동물원

Esmeralda는 $N$개의 우리가 일렬로 놓인 동물원을 만들려고 한다. 각 우리에는 동물 한 마리를 넣어야 한다. 그녀에게는 A, B, C 등으로 부르는 $K$종의 동물이 있다. 같은 동물 종을 여러 우리에 넣을 수 있지만, 바로 옆 우리에는 같은 종을 넣을 수 없다. 또한 그녀는 어떤 동물들이 서로 잘 어울리지 않는다는 것을 알고 있다. 구체적으로 $M$개의 "싸움 그룹"이 있으며, Esmeralda는 같은 싸움 그룹에 속한 두 동물을 인접한 우리에 넣고 싶어 하지 않는다. Esmeralda가 우리에 동물을 배치하는 방법의 수는 몇 가지인가?

첫 번째 줄에는 세 정수 $2\le N \le 15$, 우리의 수, $2\le K \le 10$, 동물 종의 수, $2 \le M\le 5$, 싸움 그룹의 수가 주어진다. 다음 $M$개의 줄에는 각각 $2$자 이상 $K$자 이하의 문자열이 주어진다. 이는 서로를 용납하지 않는 동물 종들의 싸움 그룹이다. 문자열에는 알파벳의 처음 $K$개 문자만 나타날 수 있고 대문자만 사용되며, 같은 문자열 안에서 같은 문자가 두 번 나타나지 않는다.

Esmeralda가 동물을 배치할 수 있는 방법의 수를 정수로 출력한다. 주어진 입력에 대해 답은 20억을 넘지 않는다.

첫 번째 예제에서는 모든 종이 서로 잘 어울린다. 첫 번째 우리에는 4종 중 하나를 넣을 수 있다. 두 번째와 세 번째 우리에는 각각 세 가지 가능성이 있는데, 바로 앞 우리와 같은 종을 넣을 수 없기 때문이다. 따라서 $4\cdot 3\cdot 3=36$가지 배치가 가능하다.

두 번째 예제에서는 비비와 코끼리가 인접할 수 없다는 것을 알고 있다. 또한 비비, 영양, 딩고, 시트론나비는 모두 적이며, 따라서 이들 중 어느 것도 서로 인접할 수 없다. Esmeralda는 코끼리를 한 칸씩 건너 배치하고 나머지 우리에는 영양, 딩고, 시트론나비 중에서 자유롭게 선택해야 한다. 코끼리로 시작하면 9가지, 다른 동물로 시작하면 9가지가 가능하다.