Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Different Standings

Limits 2s, 512 MB

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

InputOutput
3
3 1 2
3 2 2
2 3 1
Case 1: 7
Case 2: 1
Case 3: 0

Discussion

Statistics


100% Solution Ratio

kfoozminusEarliest, Nov '16

sgtlaughFastest, 157024.8s

sgtlaughLightest, 86 MB

sgtlaughShortest, 1181B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.