# DCP-131: Contest Prize Back to All Problems

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

### Problem Limits

 Language Time Limit (seconds) C 1.00 C++ 1.00 C++14 1.00 C# 1.00 Go 1.00 Java 1.00 JavaScript 1.00 Objective-C 1.00 Perl 1.00 PHP 1.00 Python 1.00 Python3 1.00 Ruby 1.00 VB.Net 1.00

# 7/24

Solve/Submission

### Ranking

# User Language Timing
01 feodorv C 0.02s
02 phoenix71 Cpp 0.07s
03 kazinayeem Cpp14 0.33s
04 sahedsohel Cpp14 0.50s
05 Robbinb1993 Cpp 0.73s
06 Morass Cpp14 0.81s
Feedback