## Beautiful Skylines

Points: 1 (partial)
Time limit: 5.0s
Memory limit: 512M

Authors:
Problem types

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

## Comments

There are no comments at the moment.