AJOB - Ajob Subsequence

You are currently studying the language Ajob (which means strange in English) from a renowned professor. The language has infinite number of letters in its alphabet (now you know, why it is called ajob).  

The professor taught you N words, one by one. The number of letters in a word is equal to it's place in the teaching order. Thus, the 1st word taught by the professor has 1 letter, 2nd word has 2 letters, 3rd word has 3 letters ... the Nth word has N letters.  

All the letters within a word are distinct to each other.

Now, you are handed an assignment. You have to choose any one of the N words and form a subsequence from it. The length of the subsequence should be exactly K less than the length of original word. For example, if the length of the chosen word is L, then the length of the subsequence should be L-K. If for any word, L is smalller than K (L < K), then you must not choose that word. Two subsequences are different to each other if, the lengths of them are different or they contain different characters in the same position.

Find the number of ways you can complete the assignment modulo p (p will always be a prime ).

Input

The first line contains T, the number of testcases. The next T lines contain three space separated integers N, K and p.

Output

For each testcase, print one integer in a single line, the number possible ways you can complete the assignment, modulo p.

Constraints

1 ≤ T ≤ 100 
2 N 1018  
0 < K < N 
2 p 105 
p
is a Prime

Example

Input:
8
2 1 2
2 1 5
5 3 13
5 2 3
6 5 11
7 6 3
6 5 7
6 5 5

Output: 1
3
2
2
7
2
0
2

Added by:Bidhan
Date:2014-08-03
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem from HackerRank

hide comments
2017-03-09 06:21:31
@Vaporeon- For 5,3,13
No. of subsequences= {Empty}----[1]+
{1,2,3,4}----[4]+
{56,57,58,59,67,68,69,78,79,89}----[10]= 1+4+10=15
15%13=2
2015-05-11 18:15:13 Vaporeon
i don't get the 5,3,13 test case.. plz help!
2014-09-29 16:09:46 yash agarwal
sir please tell me the test case where it is getting wrong.

id 12493356
2014-08-05 10:47:22 Devashish
what if L is equal to K? do we have to consider the empty set also as a subsequence ? Or am i going in the wrong direction?

Can anyone or the setter please explain any of the test case.. ?

Reply : Yes, you need to consider the empty one too.

Last edit: 2014-08-22 08:00:15
2014-08-04 13:26:16 Zeus
@Bidhan can you please check my submission and tell me where am i going wrong ??? please do reply... id: 12082573
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.