Link to Russian translation of the problem.

Kevin has a lot of permutations, but he doesn't like them. Therefore, he wants to give some of them to his friend Marv.

The permutations which Kevin has are all the permutations of numbers from 1 to N such that |Pi - i| ≤ K for all 1 ≤ i ≤ N. He determines the score of a permutation P as the product |P1 - 1|·|P2 - 2|·...·|PN - N|.

Recently, Kevin found an easy way to divide all his permutations into two groups: he gave Marv all permutations with an odd number of inversions and kept the rest.

Kevin is interested in the difference between the sum of scores of all permutations that he kept, and the sum of scores of all permutations that he gave to Marv. Help him and calculate this number modulo M.

Notes:
An inversion in a permutation P is such a pair of indices (i,j) that 1 ≤ i < j ≤ N and Pi > Pj.
By X modulo Y, we mean the number Z such that 0 ≤ Z < Y and Y divides X - Z.

Input format:

The first line of input will contain an integer T, denoting the number of test cases. Each of the next T lines of input will contain three space-separated integers N, K and M.

Output format:

For every test case, print one number on a separate line - the answer to Kevin's problem.

Constraints:
0 ≤ K < N ≤ 500
2 ≤ M < 10^4
M is a prime number
the sum of all N in each input file doesn't exceed 1000
K = N-1 in test data worth 20% of all points
N ≤ 7, T ≤ 30 in test data worth 5% of all points
N ≤ 15, T ≤ 10 in test data worth 15% of all points

SAMPLE INPUT
2
4 1 7
3 2 7

SAMPLE OUTPUT
1
4

Explanation

In the first test case, Kevin has one permutation: P = [2,1,4,3]. This permutation has two inversions, so Kevin keeps it; its score is 1.

In the second test case, Kevin has all permutations of numbers from 1 to 3. He keeps three of them with total score 4 and gives Marv the other three with total score 0.

见题面

见题面