BGC TRUST IUPC 2012

Problem B

‘C’ for Count

In how many ways you can select K objects from N different circularly placed objects such that the selection does not contain any pair of distinct objects having distance less than D around the circle? Here distance is the minimum of clockwise and anticlockwise distance. Details in following figure:

Here, 5 objects {A, B, C, D, E} are placed circularly. Say, K = 2 and D = 2, then the 5 possible selections are {A, C}, {A, D}, {B, D}, {B, E}, {C, E}. A selection is considered to be different from the others if it contains at least 1 object which is not present in the other selection.

Input

First line of the input contains a positive integer T (T <= 5000). Each of the following T lines contains three positive integers N (1 <= N <= 1000), K (1 <= K <= N) and D (1 <= D <= 10), respectively.

Output

For each case, print a line of the form Case <x>: <y>, where x is the case number and y is the number of ways modulo 1000000007(10⁹+7).

Sample Input	Output for Sample Input
4 5 2 2 5 2 1 3 2 2 10 3 2	Case 1: 5 Case 2: 10 Case 3: 0 Case 4: 50

Problemsetter: Anindya Das

Special Thanks: Md. Mahbubul Hasan