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++