Because of necessary software maintenance, Jutge.org may not work well on the afternoons of the 20th and 21th of april.
String concatenation P52564
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++