String Reconstruction

For a string S and a positive integer k, let T(S, k) be the set of all length-k substrings that appear in S. If the same substring appears multiple times, it is still included only once. For example, if S = "ABABA" and k = 2, then T(S, k) = {"AB", "BA"}.

You are given a set X of length-k strings over N kinds of characters. Count the number of strings S of length L such that T(S, k) is a subset of X.

For example, when L = 5 and X = {"ABB", "BCA", "BCD", "CAB", "CDD", "DDA"}, the only valid strings are "BCABB" and "BCDDA", so the answer is 2.

The first line contains N (1 <= N <= 26), L (1 <= L <= 100), and M (1 <= M <= 600), where M is the size of X.

The next M strings, separated by whitespace, describe the elements of X. All strings in X have the same length, and that length is at most 10. Only uppercase letters appear in the input.

Print the number of length-L strings S that satisfy the condition. The answer is less than 2^31 - 1.