TAHSINREC - Scary Secret Diary

While going through her friend’s secret diary, one-day Poga came upon a function. The function f was defined as

            f(n, k) - f(n-1, k) = f(n-1, k-1),
            f(n, 0) = 1
            and f(n, k) = 0 when n < k

Seeing how this is a recursive function, Poga got very scared. To find courage, she remembered 2 of her favorite numbers, N and K. Now she wants to find the value of f(N, K). Being a genius, it was very easy for her. Now she has challenged you to do the same too. As the answer can become very big, you should print the answer modulo M.

Input

Input starts with an integer T, denoting the number of test cases.

Then each of the next T lines contains three integers N, K, and M.

Constraints

1 <= T <= 100

1 <= N <= 105

0 <= K <= 105

1 <= M <= 1012

Output

For each test case, print the answer, value of f(N, K) modulo M.

Example

Input:
5
7 4 100
6 3 2
6 3 7
2 2 200
57217 10661734081

Output:
35
0
6
1
0

Added by:Nabil
Date:2018-09-18
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2018-10-01 00:18:17 :D
Good problem. There might be a similar already on SPOJ, but the modulo range makes it a little more interesting.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.