Tigger's bounces

Interview

Time limit1sMemory limit256 MB

Summary

Count length-K walks on an R by C grid where each step stays put or moves to a side neighbor, summed over all starts, modulo P per query.

Level: Easy3 of 10
Topics: Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

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$ .

Input

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$

Output

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$ .

Hint

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$ .

Examples3

Example 1
Input
```
2
2 2 3 10
2 2 3 100
```
Expected output
```
6
36
```
Example 2
Input
```
1
2 3 2 1000000
```
Expected output
```
20
```

Example 3

Input

3
1 1 1 1000000
20 20 1 1000000
4 5 1 7

Expected output

1
400
6