꼬치

위텍(Witek)은 그릴에 구울 꼬치를 준비하고 있습니다. 꼬치에 꽂을 수 있는 재료의 목록을 정해 두었고, 이제 어떤 순서로 꽂을지 고민하고 있습니다. 어떤 재료들은 서로 바로 옆에 놓이면 맛을 해치기 때문에 나란히 꽂을 수 없습니다. 또한 연속한 세 재료의 특정 조합도 맛이 좋지 않습니다.

예를 들어 문자 a를 파인애플 조각, 문자 b를 양고기 조각이라고 합시다. 파인애플 두 조각이 나란히 놓이는 것은 좋지 않고, 양고기가 연속으로 세 조각 놓이는 것도 좋지 않다고 합시다. 이러한 규칙은 각각 금지 조합 aa와 bbb로 나타냅니다.

꼬치는 뒤집지 않고 항상 왼쪽 끝에서부터 먹으므로, 금지 조합에서도 글자의 순서가 중요합니다.

재료를 정확히 3개 꽂아 꼬치를 만든다면, 위 규칙에서 만들 수 있는 꼬치는 aba, abb, bab, bba의 4가지입니다.

각 재료를 알파벳 소문자로 나타낼 때, 길이가 정확히 $n$인 꼬치(길이 $n$짜리 문자열) 중에서 어떤 금지된 두 글자 조합도 서로 인접하여 나타나지 않고, 어떤 금지된 세 글자 조합도 연속하여 나타나지 않는 것의 개수를 구하고, 그 개수를 $m$으로 나눈 나머지를 출력하세요. 사용할 수 있는 재료는 $p$가지이며, 알파벳의 처음 $p$개 소문자에 해당합니다.

입력의 첫 줄에는 연이어 주어지는 데이터 집합의 개수를 나타내는 작은 정수 $z$가 주어집니다.

각 데이터 집합의 형식은 다음과 같습니다.

첫 줄에는 공백으로 구분된 네 정수 $m$, $n$, $p$, $k$가 주어집니다. 이는 각각 나머지 연산의 밑, 꼬치의 길이, 서로 다른 재료의 수, 금지된 조합의 수를 의미합니다 ($1 \le m, n \le 1000$, $1 \le p \le 26$, $0 \le k \le p^2 + p^3$).

이어지는 $k$개의 줄에는 금지된 조합이 한 줄에 하나씩 주어집니다. 금지된 두 글자 조합은 알파벳 소문자 두 개로, 금지된 세 글자 조합은 알파벳 소문자 세 개로 나타냅니다. 알파벳의 $j$번째 소문자를 $\ell_j$라 할 때, 각 조합에 등장하는 모든 글자 $\ell_j$는 $1 \le j \le p$를 만족합니다.

각 데이터 집합에 대해, 조건을 만족하는 서로 다른 꼬치의 개수를 $m$으로 나눈 나머지를 한 줄에 하나씩 출력하세요.