Limits 1s, 512 MB

After researching the Coronavirus researcher come up with a solution to tackle all kinds of mutations of Coronavirus. They create N types of substances that need to push into the human body. They want to make the vaccine as P dose and also need to ensure that at least K types of substances push in each dose.

You need to find out they are how many ways to give the vaccine with P dose.

Suppose for a way the number of substances in each dose was x1,x2, …..,xP and another one is y1, y2, …., yP then to way will consider as different if there is any i (1 <= i <= P) where xi != yi

Input

Input starts with an integer T (T <= 1000000) denoting the number of test cases.

Each case starts with a line containing 3 integer N, P, K

1 <= N <= 1000

1 <= P <= 1000

1 <= K <= 1000

K*P <= N

Output

For each case, print the case number and followed by the number of ways mod 1000000009.

Sample

InputOutput
2
5 1 1
5 5 1
Case 1: 1
Case 2: 1

Submit

Login to submit.

Statistics

0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.