Problem statement

We are observing the behavior of diners in a special restaurant. The restaurant consists of M chairs arranged in a circle and N diners who arrive one at a time. A diner, when he arrives, approaches one of the chairs called his entry point. If the chair is empty, he immediately occupies it. If it is already occupied, he traverses the circle in clockwise order until he finds an empty chair. It is guaranteed that N, the number of diners, is always less than the number of chairs available, and hence each diner finds a place to sit.

If we have N diners, we can consider a sequence called entry-point sequence of the diners in the order they arrive.

Given an integer K, your task is to count the number of entry-point sequences such that after all the diners have found a chair, the chairs 1-K are occupied and the chairs M and K + 1 are empty. There are no restrictions on the occupancy of other chairs.

You have to report this number modulo a given prime P.

Input

The input file will contain several test cases. The first line contains an integer T, the number of test-cases. The succeeding lines contain the test-cases.

Input Format:

Each test-case comprises the following:

Line 1: M, N, K, P

Output

The output should contain the solutions to all the test cases, in the order of the test cases in the input. There should NOT be any blank line in the output.

Output Format:

Line 1: The answer to the instance.

POINTS and CONSTRAINTS

Total Points: 150

3 Sets:

Set 1 (10 points): 1 ≤ K ≤ N ≤ 1000

Set 2 (20 points): 1 ≤ K ≤ N ≤ 100000

Set 3 (70 points): 1 ≤ K ≤ N

Time Limit: 5 seconds

Memory Limit: 64 MB (Stack memory: 1MB)

Sample input

SAMPLE OUTPUT