MOG Round #18Ended |
Fito tiene un problema en la facultad donde está estudiando. Él tiene un password para el servidor de correo y otro para el servidor de dominio, para los dos servidores el password tiene que ser una cadena no vacía de caracteres latinos en minúscula. Los dos servidores al estar en la misma red tienen una particularidad, los dos aceptan una cadena como password si y solo si el password real es una subsecuencia. Fito tiene mala memoria para recordar los dos password por lo que quiere tener un solo password universal que los dos servidores acepten. Como Fito tiene mala memoria no puede recordar password muy grandes, por lo que quiere tener un password universal que tenga la longitud mínima. Nuestra tarea es calcular la cantidad de password que cumplan esa condición.
La entrada consiste en dos líneas, cada una contiene el password real de cada servidor. La longitud de estos password no exceden los 2000 caracteres.
Debe de imprimir en una línea la cantidad de password universales de longitud mínima módulo 10^9+7
En el segundo ejemplo los password de menor longitud son: abcaba, abcbab, acbcab, cabcab.