String concatenation P52564


Statement
 

pdf   zip

thehtml

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 1018, 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 109 + 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++