Medium Divide and Conquer > Dynamic Programming

Suppose this year there are K students to participate in ACM ICPC Dhaka Regional 2016 from your university. So, you arranged a contest at DevSkill to find the best from bests. After the completion, every one of the K participants can get a rank between 1 to K, and there are no two students whose ranks are the same. To enable all the K students to participate in the contest, your university decide to distribute scholarship to the K participants according to their ranks. At first your university authorities provide N scholarship which are the same, and then distribute the N scholarships with the rules of this: 1. **The number of scholarships the student ranking i gets cannot be less than the number of scholarships the student ranking i +1 gets.** 2. **Every student at lest gets one scholarship.** 3. **At last there is no scholarship left.** ---------- If N=4 and K=3, there are only one way to distribute the scholarships: the student ranking 1 gets 2 scholarships, the student ranking 2 gets 1 scholarship, and the student ranking 3 gets 1 scholarship. Now give the N and K, you just tell me after the competition, how many different ways to distribute the N scholarships to the K participants. As the result may be very large, print the result module 1000000009 for the output. Input: ------ The first line of input is the number of test cases **(1 ≤ T ≤ 1000)**. For each test case: There is only one line with two integers: **N (1≤ N ≤1000)** and **K (1 ≤ K ≤ 1000)** Output: ------- For each test case, output one line containing "Case x: “, where x is the test case number, followed by the expected answer.See the sample I/O. Sample Input ------------ 2 4 3 10 3 Sample Output ------------- Case 1: 1 Case 2: 8

Rezwanul Islam Maruf