Su tarea consiste en calcular el número de cadenas de longitud ~n~ que tienen como subcadena un patrón dado de longitud ~m~. Todas las cadenas constan de caracteres de la ~A~ a la ~Z~.

Entrada

La primera línea de entrada contiene un entero ~n~: la longitud de la cadena final. La segunda línea contiene un patrón de longitud ~m~.

Salida

Imprima el número de cadenas módulo ~10^9+7~.

Restricciones

• ~1 \leq n \leq 1000~
• ~1 \leq m \le 100~

Ejemplo de Entrada

6
ABCDB

Ejemplo de Salida

52

Explicación: La cadena final tendrá la forma ~ABCDBx~ o ~xABCDB~, donde ~x~ es cualquier carácter entre la ~A~ y la ~Z~.