Matcom Online Grader

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.

Input

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.

Output

Debe de imprimir en una línea la cantidad de password universales de longitud  mínima módulo 10^9+7

Sample test(s)

Hints

En el segundo ejemplo los password de menor longitud son: abcaba, abcbab, acbcab, cabcab.