String concatenation P52564

Statement

How many different words of length exactly $\ell$ can you build by concatening $m$ given words? You can use any word as many times as you wish.

Input

Input consists of several cases, each with $\ell$ and $m$ , followed by $m$ different words. Assume that $\ell$ is between 1 and $10^{18}$ , that $m$ is at least 1, that the words only have lowercase letters, and that the sum of their lenghts is at most 50.

Output

For every case, print the result modulo $10^9 + 9$ .

Public test cases

Input

1 3 a deu hol
4 3 a deu hol
100 2 a aa
4 3 a ab ac
8 3 hola lola la
10 3 ab abb bb
10 4 x y yy xyy
32 4 wo lo wolo wololo
3 4 ab c a bc
1000000000000000000 4 ab c a bc

Output

Information

Author: Pol Mauri
Language: English
Official solutions: C++
User solutions: C++