Required Substring.

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Java, JS, Kotlin, Lisp, Lua, ObjC, OCaml, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, ~~Swift~~, TCL, Text, Turing, VB, Zig

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

Entrada

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

Salida

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

Restricciones

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

Ejemplo de Entrada

6
ABCDB

Ejemplo de Salida

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

Comments

There are no comments at the moment.