동물원

Esmeralda는 긴 일렬로 $N$개의 우리를 갖춘 동물원을 짓고 있다. 각 우리에는 동물 한 마리를 넣어야 한다. 선택할 수 있는 동물 종은 $K$가지이며, 이를 A, B, C, 기타 등등으로 부른다. 같은 동물 종을 여러 우리에 넣을 수 있지만, 서로 바로 옆에 넣을 수는 없다. 또한 일부 동물들은 서로 잘 지내지 못한다는 것을 알고 있다. 더 구체적으로, 동물 종으로 이루어진 $M$개의 ``다투는 그룹''이 있으며, Esmeralda는 같은 다투는 그룹에 속한 두 동물을 서로 인접한 우리에 넣고 싶지 않다. Esmeralda가 우리에 동물을 배치하는 방법은 몇 가지인가?

점수

여러 테스트 케이스 그룹으로 풀이를 평가한다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

케이스 | 배점 | 제한

$1$ |$20$| $N \le 10$, $K \le 5$, $M=0$

$2$ |$40$| $N \le 10$, $K \le 5$

$3$ |$20$| $M \le 1$

$4$ |$20$| 추가 제한 없음.

첫 번째 줄에는 세 정수 $N$ ($2 \le N \le 15$), $K$ ($2 \le K \le 10$), $M$ ($0 \le M \le 5$)가 주어진다. 각각 우리의 수, 동물 종의 수, 다투는 그룹의 수이다.

이어지는 $M$개의 각 줄에는 길이가 $2$ 이상 $K$ 이하인 문자열이 주어진다. 이는 서로 어느 두 종도 용납하지 않는 동물 종들의 다투는 그룹이다. 문자열에는 알파벳의 처음 $K$개 문자만 나타날 수 있으며 대문자만 사용된다. 같은 문자열에 한 문자가 여러 번 나타나지 않는다.

입력은 답이 항상 2십억을 초과하지 않도록 주어진다.

Esmeralda가 동물을 배치할 수 있는 방법의 수를 나타내는 정수 하나를 출력한다.

첫 번째 예제에서는 모든 종이 서로 잘 지낸다. 첫 번째 우리에서 Esmeralda는 4가지 동물 종 중 하나를 선택할 수 있다. 두 번째와 세 번째 우리에는 각각 세 가지 선택지가 있는데, 바로 앞 우리의 종과 같을 수 없기 때문이다. 가능한 배치는 총 $4\cdot 3\cdot 3=36$가지이다.

두 번째 예제에서는 Babian과 Elefant를 서로 인접하게 놓을 수 없다는 것을 알고 있다. 또한 Babian, Antilop, Dingo, Citronfjäril은 모두 서로 적이며, 따라서 이들 중 어느 둘도 서로 인접하게 놓을 수 없다. 그러므로 Esmeralda는 한 칸씩 건너 모든 다른 우리에 Elefant를 넣고, 나머지 우리에서는 Antilop, Dingo, Citronfjäril 중 하나를 자유롭게 선택해야 한다. Elefant로 시작하면 9가지 방법이 있고, 다른 동물 중 하나로 시작하면 9가지 방법이 있다.