Migrated from Lutece 820 Round Table

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

I have $m$ little buddies, and tonight we will have a fancy dinner in my room.

Fortunately, I have a round table which is large enough for all my little buddies. (As for me, I will not sit in the round table for some reasons) And the round table is so large that I will not let my little buddies sit shoulder to shoulder.

That means I will select $m$ seats from $n$ seats, and there maximal length of consecutive seats in the original round table won't be larger than or equal to $k$. I want know how many different ways I can choose.

Here is one more thing, two ways are considered the same if and only if one can be obtained by rotation.

The answer may be very large so the answer should modulo $10^9+7$.

Input

The first line has a number $T$ ($T\leq 200$) , indicating the number of test cases.

Next each line contain three integer $n$, $m$, $k$ ($1\leq n\leq 10^5$, $1\leq m\leq 10^5$, $2\leq k\leq 10^5$, $m\leq n$).

Output

For every case, you should output Case #t: at first, without quotes. The $t$ is the case number starting from $1$.

Then follows the answer, See the sample for more details.

Samples

3
3 1 2
5 2 2
8 3 2

Case #1: 1
Case #2: 1
Case #3: 2

Resources

2013 ACM/ICPC Asia Regional Chengdu Online