All submissions for this problem are available.
On Titan, the moon of planet Jupiter, there are N craters that exist on a straight line of length N-1 units. For simplicity lets number
them from 1 to N and further assume that adjacent craters are separated by exactly 1 unit.
The Titan Gods which are a total of M in number decide to play in this arena of craters by moving from one crater to another. The protocol
that they follow while moving are as follows:
- At the onset of the play, all Gods occupy the first M craters, one God per crater.
- For the same God the distance between two consecutive craters where God stops is at most D units.
- Gods can move from only left to right. (assume that crater number one is the leftmost one).
- In each crater exactly one God has to reside.
- At the end of the game play all the Gods must occupy the last M craters.
You are asked to evaluate the number of possible ways in which the game can be played.
- The first line of the input contains an integer T denoting the number of test cases.
- The first line of each test case contains 3 integer N M D
- If game can be played in X ways, output X modulo 31037
- 1 ≤ T ≤ 30
- 1 < N < 10^9
- 1 < D ≤ 10
- M < N
- 1 < M ≤ D
Input: 4 10 4 5 5 2 3 30 4 7 9 3 3 Output: 29 3 269 1
|Time Limit:||1 - 8 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.