Error Crítico de Lectura#3448

Error Crítico de Lectura

1 segundo
128 megabytes

Se te dan cadenas s_1, s_2, \ldots, s_k que consisten en letras latinas minúsculas.

Encuentra la cantidad de cadenas de longitud que consisten en letras latinas minúsculas que no contengan ninguna de las cadenas s_1, s_2, \ldots, s_k como subcadena (una secuencia contigua de caracteres). Dado que este número puede ser grande, imprímelo módulo .

Entrada

La primera línea contiene dos enteros y k~(1 \le n \le 10^9, 1 \le k \le 10) — la longitud de las cadenas a contar y la cantidad de cadenas prohibidas.

Cada una de las siguientes líneas contiene una cadena s_i. Cada cadena consiste en letras latinas minúsculas y tiene longitud entre y inclusive.

Salida

Imprime un único entero — la cantidad de cadenas de longitud que no contienen ninguna de las cadenas s_i como subcadena, tomado módulo .

Ejemplos

Ejemplo 1

Loading
Loading

Ejemplo 2

Loading
Loading

Ejemplo 3

Loading
Loading