DestinyLand is a really fun place for kids. It is composed of N islands, numbered from 1 to N. The company is planning to divide these N islands into exactly M area, such that, each island will belong to one of the M areas, and each area will contain at least one island.

Now the company is going to build bridges between the islands. Each area should be isolated from another. So the bridges can be built, only if both the endpoint islands belong to the same area. That is, in total they will build exactly n-m bridges to maintain connectivity within each area. (Of course, they won't build more than N-M bridges because that cost too much!)

For area to area connections, the company planned to build a harbor to one chosen island in each area. Due to heavy traffic, each of the chosen islands should NOT directly connect with more than K bridges. Can you help the company figure out how many bridge and harbor construction layouts are possible?

Note that all harbors are the same, all bridges are the same, but islands are distinct.

Input Format

The first line contains an integer T indicating the number of test cases.

For each test case, there are four space separated integers N M K MOD

Output Format

For each test case, print the number of layouts modulo MOD

Constraints

1 ≤ T ≤ 10

1 ≤ N ≤ 10^{9}

1 ≤ M , K ≤ min(N, 100)

1 ≤ MOD ≤ 2*10^{9}

Sample Input

3
3 2 1 1000003
3 1 2 1234567891
3 1 1 314159

Sample Output

6
9
6

见题面

见题面