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
hide comments
ricky99999:
2017-03-09 06:21:31
@Vaporeon- For 5,3,13
|
|
Vaporeon:
2015-05-11 18:15:13
i don't get the 5,3,13 test case.. plz help! |
|
yash agarwal:
2014-09-29 16:09:46
sir please tell me the test case where it is getting wrong.
|
|
Devashish:
2014-08-05 10:47:22
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?
|
|
Zeus:
2014-08-04 13:26:16
@Bidhan can you please check my submission and tell me where am i going wrong ??? please do reply... id: 12082573 |
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 |