Tigger's bounces

Tigger loves to bounce. Today he spent the whole day in a rectangular field that is $R$ cells wide and $C$ cells long.

With one bounce Tigger lands on one of the four cells that share a side with the cell he is on, above, below, left or right, or he lands again on the same cell. He never lands outside the field.

Write down the cells Tigger lands on in order and you get a sequence of length $K$. The first landing may be on any cell of the field, and every landing after that follows the rule above. Once Tigger lands for the $K$th time, the day's bouncing is over.

Write a program that counts the different ways Tigger can bounce and prints the count modulo $P$.

The first line has a positive integer $Q$, the number of questions. $Q$ is at most $10$.

Each of the next $Q$ lines holds one question: the positive integers $R$, $C$, $K$, $P$ in that order, separated by single spaces.

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

Print $Q$ lines, one answer per question, in the order the questions are given. Each line holds the number of different ways Tigger can bounce, modulo $P$.

Take $R = 2$, $C = 2$, $K = 3$. On a $2 \times 2$ field every cell has three possible next landings, counting the cell itself. There are four choices for the first cell and three choices for each of the two later bounces, so the count is $4 \times 3 \times 3 = 36$.