Problem
In the First City of Mars there are N bus stops, all aligned in a straight line of length N1 km. The mayor likes to keeps things simple, so he gave the bus stops numbers from 1 to N, and separated adjacent stops by exactly 1 km.
There are also K buses in the city. The mayor has to plan the bus schedule and he would like to know in how many ways that can be done. This number can be very large. Luckily there are a few constraints:
Help the mayor evaluate the number of schedules. However try not to give him very bad news (a lot of schedules) so just output the real number modulo 30031.
Input
The first line in the input file is the number of cases T.Output
For each case output the number of ways to plan the bus schedules (modulo 30031) in the format "Case #t: [number of ways modulo 30031]" where t is the number of the test case, starting from 1.Limits
1 < T ≤ 30
1 < P ≤ 10
K < N
1 < K ≤ P
Small dataset
1 < N < 1000
Large dataset
1 < N < 10^{9}
Sample
Input 
Output 
3

Case #1: 1

Let's name the buses: A, B, C...
For the first case there is only one possible way of planning the schedule: A → 1, 4, 7, 10. B → 2, 5, 8. C → 3, 6, 9.
For the second case the possible ways of planning are:
(A → 1,3,5. B → 2,4),
(A → 1,3,4. B → 2,5),
(A → 1,4. B → 2,3,5).
Points  Correct  Attempted 

8pt  51  57 
26pt  16  23 