Time table Arrangements

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.$

Constraints

$1<=$ T $<=10$

$1<=$ N$,$ M$,$ K $<=10^3$

Note: If no arrangement is possible print $0.$

Sample Input

$2$

$112121$

Sample output

$21$

Explanation

Testcase $1$: The possible arrangements are PC and CP$.$

Testcase $2$: The only possible arrangement is CPC$.$ C$++$ code