Critical Misread#3448

Critical Misread

1 secondo
128 megabyte

Vi vengono date stringhe s_1, s_2, \ldots, s_k composte da lettere latine minuscole.

Trovate il numero di stringhe di lunghezza composte da lettere latine minuscole che non contengano nessuna delle stringhe s_1, s_2, \ldots, s_k come sottostringa (una sequenza contigua di caratteri). Poiché questo numero può essere grande, stampatelo modulo .

Input

La prima riga contiene due interi e k~(1 \le n \le 10^9, 1 \le k \le 10) — la lunghezza delle stringhe da contare e il numero di stringhe proibite.

Ciascuna delle successive righe contiene una stringa s_i. Ogni stringa è composta da lettere latine minuscole e ha lunghezza compresa tra e inclusi.

Output

Stampate un singolo intero — il numero di stringhe di lunghezza che non contengono nessuna delle stringhe s_i come sottostringa, modulo .

Esempi

Esempio 1

Loading
Loading

Esempio 2

Loading
Loading

Esempio 3

Loading
Loading