How many different words of length exactly ℓ 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 ℓ and m,
followed by m different words.
Assume that ℓ 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**

1 5 1 11 11 56 1024 65536 15 382802655

Information

- Author
- Pol Mauri
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Quinzè Concurs de Programació de la UPC - Semifinal
- Date
- 2017-06-29