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 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**

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

Input | Output |
---|---|

2 5 1 1 5 5 1 | Case 1: 1 Case 2: 1 |