문자열 복원하기

문자열 S와 양의 정수 k에 대해, S에 등장하는 길이 k의 부분문자열들의 집합을 T(S, k)라고 하자. 같은 부분문자열이 여러 번 등장해도 집합에는 한 번만 포함된다. 예를 들어 S = "ABABA", k = 2이면 T(S, k) = {"AB", "BA"}이다.

N종류의 문자로 이루어진 길이 k 문자열들의 집합 X가 주어진다. 길이가 L인 문자열 S 중에서 T(S, k)가 X의 부분집합이 되는 것의 개수를 구하라.

예를 들어 L = 5이고 X = {"ABB", "BCA", "BCD", "CAB", "CDD", "DDA"}인 경우, 조건을 만족하는 문자열은 "BCABB"와 "BCDDA" 두 개이다.

첫째 줄에 N(1 <= N <= 26), L(1 <= L <= 100), M(1 <= M <= 600)이 주어진다. M은 집합 X의 크기이다.

이어서 X에 속한 M개의 문자열이 공백으로 구분되어 주어진다. X의 모든 문자열은 길이가 같고, 그 길이는 10 이하이다. 입력에는 대문자만 사용된다.

조건을 만족하는 길이 L 문자열 S의 개수를 출력한다. 정답은 2^31 - 1보다 작다.