Bhanderi is a kind-hearted person. He loves giving away things.

He has N candies. There are M students waiting in a line to collect candies. The students take turns to collect candies, since he does not want some students to have way more candies than other, he has decided that no student will get more than C candies, but a student may get 0 candies ( Yes, he will feel bad but it's okay ).

Formally for each student, if the number of candies received is x then $0 <= x <= C$

He wants to find the number of ways to divide the candies among the students. Two ways are different if atleast one student receives different amount of candy.

But, Bhanderi is not able to find the total number of ways. Help poor Bhanderi solve the task at hand!

Input format

The first line of input contains T denoting the number of test cases

The only line of input for each test case contains three space separated integers N M C

Output format

Output one integer per line per test case, since the number of ways can be pretty huge, output is modulo $10^9 + 7$

Constraints

• $1<=T<=100$
• $1<= N <= 10^5$
• $1<= M <= 10^5$
• $1<= C <= 100$

Sub-tasks

For 25% points : $1<= N, M, C <= 10$

For 75% points : original constraints