티거의 뜀박질

티거는 통통 뛰어오르기를 아주 좋아한다. 오늘 티거는 가로 $R$칸, 세로 $C$칸인 직사각형 풀밭에서 하루 종일 뛰어놀았다.

티거는 한 번 뛰어오를 때 지금 있는 칸과 변을 맞대고 있는 위, 아래, 왼쪽, 오른쪽 네 칸 중 한 칸에 내려앉거나, 같은 칸에 그대로 다시 내려앉는다. 풀밭 밖으로는 내려앉지 못한다.

티거가 내려앉은 칸을 순서대로 적으면 길이가 $K$인 수열이 된다. 처음 내려앉는 칸은 풀밭의 어느 칸이어도 되고, 그다음부터는 위의 규칙을 지킨다. $K$번째로 내려앉으면 그날의 뜀박질이 끝난다.

서로 다른 뜀박질 방법의 수를 $P$로 나눈 나머지를 구하는 프로그램을 작성하시오.

첫째 줄에 질문의 개수 $Q$가 주어진다. $Q$는 $10$ 이하의 양의 정수다.

다음 $Q$개의 줄에 질문이 한 줄에 하나씩 주어진다. 각 줄에는 양의 정수 $R$, $C$, $K$, $P$가 이 순서대로 공백 한 칸으로 구분되어 주어진다.

$1 \le R, C \le 20$, $1 \le K \le 1000$, $1 \le P \le 1000000$

$Q$개의 줄에 질문이 주어진 순서대로 답을 한 줄에 하나씩 출력한다. 각 줄에는 티거가 뛰어놀 수 있는 서로 다른 방법의 수를 $P$로 나눈 나머지를 출력한다.

$R = 2$, $C = 2$, $K = 3$인 경우를 보자. $2 \times 2$ 풀밭에서는 어느 칸에서든 다음에 내려앉을 수 있는 칸이 자기 자신을 포함해 세 개다. 처음 칸을 고르는 방법이 네 가지이고 그 뒤 두 번의 뜀박질이 각각 세 가지이므로, 방법의 수는 $4 \times 3 \times 3 = 36$이다.