Little Peter is collecting stamps. Recently, he went shopping with his mother Lucia and guess what: As they were going around the post office, he started to blackmail his mom, as only the little boys can. At the post office, they were selling N different types of one-dollar stamps and M different types of two-dollar stamps.
Peter got exactly K dollars from his mom, and he wants to spend all of them on stamps. Note that he can buy more stamps of the same type. You may assume that the post office has an infinite stock of each type of stamp.
Now, Peter is wondering in how many ways he can buy the stamps.
Problem specification
Given are the integers N, M, K, and a prime number P.
Your task is to compute the value Z mod P, where Z is the (possibly huge) number of ways in which Peter can spend all K dollars on stamps.
Input specification
The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of a single line containing the integers N, M, K, and P.
You may assume that 3 ≤ P ≤ 1000000.
For the small input set, you may assume that 0 ≤ N,M ≤ 1000 and 1 ≤ K ≤ 1000.
For the large input set, you may assume 0 ≤ N,M ≤ 300 and 1 ≤ K ≤ 1000000000000 = 1012.
Output specification
For each test case output a single line with a single integer: The number of different ways to buy stamps, modulo P.
Example
In the first test case, we must buy one 2-dollar stamp and there are 10 types.
In the second test case, we have these options:
– buy two 2-dollar stamps: 3 ways to do so
– buy a 2-dollar stamp and two 1-dollar stamps: 2 × 3 = 6 ways to do so
– buy four 1-dollar stamps: 5 ways to do so
Therefore the answer is (3 + 6 + 5) mod 47 = 14 mod 47 = 14.