There are $m$ persons and $n$ chairs. Each person needs to maintain social distance between themselves and the person they are sitting next to. Therefore, once a person sits, the person who sits next to them sits at a distance that is in multiples of the integer $k$.

Your task is to find the total number of arrangements possible so that all the people can be seated. Print your answer modulo $10^9 + 7$.

Notes

• All the people must get a chair to sit on
• Two arrangements are different either if the state of a chair is different in both cases or if two different people are seated on it. For example, for $n=10$ chairs, $m=2$ persons, and $k=2$, if the first person sits at the 2nd position, then the second person can sit only at the 4th, 6th, 8th, or 10th position.

Input format
The first line contains an integer $t$ representing the number of test cases.

Each of the next $t$ lines contains three integers $n$, $m$, and $k$.

Output format

Print $t$i ntegers where the $i^{th}$ integer is the total number of arrangements for the $i^{th}$test case.

Constraints

$1 \leq t \leq 10^{5}$

$1 \leq {n,m,k} \leq 10^{6}$