The 2016 Olympic Games is over, but in a planet far away from earth, there is a similar competition going on. Athletes from not only all countries in that planet but also from neighboring planets take part in that prestigious competition. As the number of participants is huge and a large number of them have same level of expertise, there are lot of ties for a place. The judges have also noticed that because of lot of ties, there are sometimes very few places in the ranklist compared to the number of participants.
They are interested to know how many different standings can be created with n athletes taking part in a competition when there will be at least r athletes tied in every place and at most k places can be present in the standings/ranklist. A standing X is different from another standing Y if and only if one of the following conditions are satisfied:
- There are different number of places in the standings X and Y.
- There are equal number of places in both standings, but there exists at least one place such that the set of athletes in that place in standing X is different from the set of athletes in the same place in standing Y.
For example, say n=3, r=1 and k=2. Let us denote the athletes with integers from [1,...,n]. Now, all of them can tie in the 1st place (1 way), or 2 athletes may tie in the 1st place (in 3 ways) or just one athlete may claim the 1st place (in 3 ways) and the remaining (1 or more) athletes have no other option than to be at the 2nd place. As k=2, there can not be any 3rd place in the standing. The following standings can be formed: ({1, 2, 3}), ({1}, {2, 3}), ({2}, {1, 3}), ({3}, {1, 2}), ({2, 3}, {1}), ({1, 3}, {2}), ({1, 2}, {3}). Therefore, the total number of standings will be 7.
Input
The first line of input contains a single integer, T (T≤105). Then T lines follow. Each of these T lines will contain 3 integers: n (2 ≤ n ≤ 104), r (1 ≤ r ≤ 20) and k (1 ≤ k ≤ 100).
Output
For each of the cases output "Case x: y" in a separate line, where x is case number and y is the number of different possible standings. As this number can be quite large, output y modulo 1000,000,007.
Sample
| Input | Output |
|---|---|
3 3 1 2 3 2 2 2 3 1 | Case 1: 7 Case 2: 1 Case 3: 0 |
