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 |P_i - i| ≤ K for all 1 ≤ i ≤ N. He determines the score of a permutation P as the product |P₁ - 1|·|P₂ - 2|·...·|P_N - 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 P_i > P_j.

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⁴
• 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