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.
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.
The first line of the input file contains an integer T<=105 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, and 0 ≤ N,M ≤ 300 and 1 ≤ K ≤ 1000000000000 = 1012.
For each test case output a single line with a single integer: The number of different ways to buy stamps, modulo P.
3 0 10 2 47 2 2 4 47 5 5 10 47
10 14 6
Migrated from old NTUJ.
IPSC2010 problem L
| No. | Testdata Range | Score |
|---|