The Placement Season has started at the Aliens’ College of Machine Learning (ACM) and as expected, every alien of the college is burning the candle at both ends. William Archer (WA), the topper and the most eligible bachelor of ACM is however indifferent towards the situation. He has been spending all his time with his friend Rihanna the Exuberant(RTE) and ignoring his studies. RTE, being the more mature and sensible of the two, devises a plan for WA so that he could spend adequate time with her without compromising his studies. Upon consultation with her best friend AC, she comes up with the following plan for WA:

1. She divides WA's next N hours into K sessions.
2. Each session can last for x hours where x is an integer and 1 <= x <= M.
3. In each session, WA can either study or meet RTE.
4. If WA is studying in one session, he must meet RTE in the next session and vice versa.
5. WA must always study in the first session.

You have been hired by WA to calculate how many different timelines can RTE prepare for the next N hours.

Input

The first line specifies the number of test cases T and the next T lines contain 3 integers each: N, K and M.

Output

For every test case print a single integer which is the number of different ways RTE can prepare WA's timeline for the next N hours. Print your answer modulo 1000000007.

Constraints

T <= 100
1 <= N, K, M <= 100000
K <=N

Example

Input:
3
4 3 2
7 4 3
1 1 1

Output:
3
16
1

Explanation for Sample Input 1

RTE can prepare the following three schedules for the next 4 hours

S | MM | S
SS | M | S
S | M | SS

where S indicates that WA should be studying that hour, and M indicates that he should be meeting RTE that hour.

Note that WA has to start with his studies always in order to satisfy Point 5 of the plan.