Codah ClubTrain. Submit. Improve.
Sign in
English
#0001E2

BubbleDecorations

For next year’s Bubble Cup the organizers thought of the possible decorations that could be arranged. One idea was to create a string of balloons that could go all around the competition arena. The problem is that the director of competition likes only certain sequences of balloon colors to be used for the string. For example, if there are four different colors: A, B, C and D, the director might say that only the sequences ABB, BCA, BCD, CAB, CDD and DDA can be used for decoration. If the length of the string was 5, then the only possible arrangements could be BCABB and BCDDA (strings such as ABBCA could not be used because BBC is not an approved sequence). Since the director likes variety, it is important to know the total number of arrangements possible, given the list of approved sequences.


InputInput consists of two lines. The first line will contain three positive integers N, L and M, 1 ≤ N ≤ 26, 1≤ L ≤ 100, 1 ≤ M ≤ 600, where N indicates the number of different colors, L is the length of the arrangements we want to create and M indicates the number of sequences which the director likes. The next line will contain m sequences. Each sequence will be of the same length (between 1 and 10) and will be separated by a single space. All sequences will consist only of uppercase letters of the alphabet.

OutputOutput should be a single line containing the number of possible arrangements. All answers will be within the range of a 32-bit integer.


Input:
4 5 6
ABB BCA BCD CAB CDD DDA
Output:
2


Input:
5 4 5
X Y Z W Q
Output:
625


Input:
4 8 3
AA BB CC
Output:
3

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.