You are an architect designing a city, and you have decided that you are going to make it beautiful, or more specifically, that it is going to have a beautiful skyline. A skyline consists of \(N\) consecutive, unit width buildings, each with a height between \(0\) and \(H\) inclusive. It is considered beautiful if the height of two directly adjacent buildings differs by no more than \(K\). In order to design your beautiful city, you first want to know how many different beautiful skylines are possible.

Consider a skyline where \(N=6\) and \(H=4\). We represent a building a single column, where x indicates where a building is:

..x...
x.x...
xxx.x.
xxxxx.

The third and fourth buildings differ in height by \(3\). Thus, this is only a beautiful skyline if \(K\geq 3\).

Input Specification

The input will start with an integer \(T\), the number of test cases to follow. Each test case consists of a line containing three integers: \(N\), the number of buildings in your skyline, \(H\), the maximum possible height of a building in the skyline and \(K\), the maximum number of units of height that two adjacent buildings can differ by in order to be a beautiful skyline.

Output Specification

For each test case in the order given, output a single line containing a single integer, the number of beautiful skylines there are modulo \(10^9+7\).

Bounds

Note this problem includes sub-problems of increasing difficulty worth different numbers of points:

• 50 points: \(1 \leq N, H, K \leq 100\)
• 100 points: \(1 \leq N, H, K \leq 2000\)
• 150 points: \(1 \leq N \leq 10^9\) and \(1 \leq H, K \leq 100\)

Important Note: Observe that the 150 point sub-problem is not a superset of the 100 point sub-problem. You may need to implement some sort of conditional logic to switch algorithms.

For all sub-problems:

\(1 \leq T \leq 10\)

Sample Input

4
2 2 2
2 2 1
3 2 1
50 50 20

Sample Output

9
7
17
785605991