시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 4 2 1 100.000%

문제

어떤 문자열 S의 길이가 k인 부분문자열의 집합을 T(S, k)라 표현하자. 예를 들어 S="ABABA", k=2일 때, T(S, k)={"AB", "BA"}가 된다. {"AB", "BA", "AB", "BA"}가 아닌 이유는 집합은 같은 원소(중복된 원소)를 허용하지 않기 때문이다.

N 종류의 문자로 이루어진 길이가 k인 문자열들의 집합 X가 주어졌을 때, T(S, k)가 X의 부분집합이 되도록 하는 S의 개수를 구하는 프로그램을 작성하시오. 단 S의 길이는 L이어야 한다.

예를 들어 X={"ABB", "BCA", "BCD", "CAB", "CDD", "DDA"}인 경우에는 "BCABB", "BCDDA"의 두 가지 경우가 있다.

입력

첫째 줄에 N(1≤N≤26), L(1≤L≤100), M(1≤M≤600)이 주어진다. M은 집합 X의 크기이다. 다음 줄에는 X를 이루는 문자열들이 주어진다. 각 문자열들의 길이는 같으며, 10 이하이다. 입력으로는 대문자만 주어진다.

출력

첫째 줄에 S의 개수를 출력한다. 이 값은 32-bit signed integer(VC에서 int)의 범위를 넘지 않는다.

예제 입력

5 4 5
E D C B A

예제 출력

625

힌트