Marbles

How many different ways you can distribute N (distinguishable) marbles into K boxes where each box should contain at least X marbles? Two distributions are considered different if there is at least one marble which is contained by different boxes in the distributions.

Input

First line of the input contains T (1 ≤ T ≤ 50) which is the number of test cases. Each of the following T lines contains three space separated integers N , K and X (1 ≤ X ≤ N ≤ 100000 and 1 ≤ K ≤ 50).

Output

Output the case number, followed by the required quantity. Output the result modulo 1000000007. Note: For the 1st case the possible distributions are (the i-th element is the box number for the i-th marble) : {1,1,2,2}, {1,2,1,2}, {1,2,2,1}, {2,2,1,1}, {2,1,2,1}, {2,1,1,2}.

#13043Marbles

Input

Output