TAMADOM - PKP Knows Nothing 2
"You know nothing, PKP Snow"
PKP Snow is tired of hearing this. Now he wants to prove that he does know something!
He has N distinct dragonglass knives in front of him. He needs to choose R knives out of these. Everyone thinks PKP doesn't know how many ways he can choose R knives out of N. Help PKP finding the answer and thus prove them wrong. But the answer can be very big, so PKP will tell the answer modulo M.
Given N, R, M, your job is to find the answer for PKP.
Input
Input starts with an integer T, denoting the number of test cases. Then each of next T lines contains three integers N, R and M.
Constraints
1 <= T <= 100
1 <= N <= 100000
0 <= R <= 100000
1 <= M <= 1000000000000
Output
For each test case, print the answer PKP has to find, number of ways to choose R knives out of N modulo M. Print each answer in separate lines like in sample output.
Example
Input: 5 5 3 100 5 3 2 5 3 7 1 1 20 100 50 1000000009 Output: 10 0 3 1 933591892
Explanation
PKP can choose 3 knives out of 5 knives in 10 ways. 10 modulo 100 is 10, while 10 modulo 7 is 3. A modulo B means the remainder found after dividing A by B.
[Original Setter of this problem is Tahsin Masrur, RUET ]
Added by: | Avik Sarkar |
Date: | 2018-05-30 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | RUET Beginner Battle -1 |