FastPrep

Description

Solutions

Find Arrangements

📚RELATED PROBLEMS

Anju teaches Physics and Chemistry for P and C number of hours respectively. After teaching a particular subject for more than N number of hours continuously, Anju gets exhausted and needs to switch to another subject.

So the Principal has decided to schedule the time table for Anju in such a way that she does not teach a given subject for more than N number of hours continuously. The principal being weak in maths asks you to find out the maximum number of possible arrangements of hours in which Anju can teach a given subject for no more than N number of hours continuously.

Input format

First line contains T the required number of test cases.
Next T lines contain Three space-separated integers P, C, and N respectively.

Output format

For each test case, print the number of arrangements of hours in which Anju has not to teach a given subject for more than N number of hours continuously modulo 10^9+7.

Note: If no arrangement is possible print 0.

Example 1:

Input:  P = 1, C = 1, N = 2
Output: 2 
Explanation:
N/A

Example 2:

Input:  P = 1, C = 2, N = 1
Output: 1 
Explanation:
N/A

Constraints:

1 ≤ T ≤ 100
1 ≤ P, C, N ≤ 10^3