All Submissions


College days are nearing it's end and this is making Sunny really SAD (for obvious reasons :P). He , being sad that he is, spends an awful lot of time listening to sad songs on his cell phone. He currently has N songs all of which happen to be sad. He also has this weird habit of always listening to P songs continuously. His cell phone generates a playlist of P sad songs according to two rules - Each song has to be played at least once and At least M songs have to be played between any two occurrences of the same song (As he gets really sad when he listens to same song too frequently).

Sunny, trying to divert his mind from sadness, wonders how many distinct playlists his cell phone can create.He needs your help.

Input
First line contains T denoting the number of test cases and Then T lines follow each containing 3 Integers denoting N, M and P respectively.

Output
A Single Integer for each test case denoting the number of playlists % 1000000007.

Constraints

T<=111
1<=N<=100
0<= M <= N
N<=P<=100

Sample Input

2
1 0 3
1 1 3



Sample Output

1
0


Problem Setter : Arjun Singh Bhatia


Languages: AWK,Bash,Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0