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.
2 5 1 1 5 5 1
Case 1: 1 Case 2: 1