No.1011 Infinite Stairs
otamay6
Lemma299
polylogKProblem Statement
There is an infinitely long staircase. You are initially on step $0$ and intend to repeat the following action $N$ times.
・When you are on step $i$, move to one of steps $i+1$, $i+2$, $\dots$ , $i+d$
Find the number of ways of moving such that you arrive at step $K$ after $N$ moves.
Since the answer can be very large, find the remainder when it is divided by $10^9+7$
Input
$N\ d\ K$
All inputs are given as integers
$1 \le N,d \le 300$
$N \le K \le d \times N$
Output
Output the number of ways of moving such that you arrive at step $K$ after $N$ moves.
Print a newline at the end.
Sample
Sample 1
Input
3 2 5
Output
3
There are 3 ways of moving: (2,2,1), (2,1,2), (1,2,2)
Sample 2
Input
6 3 10
Output
90
Among the possible ways of moving, those in ascending order are the 3 ways (1,1,1,1,3,3), (1,1,1,2,2,3), (1,1,2,2,2,2), and the number of rearrangements of any of these is
${}_{6}{\rm C}_{2}$ + ${}_{6}{\rm C}_{3}\times {}_{3}{\rm C}_{2}$ + ${}_{6}{\rm C}_{2}$ = 90 ways
Sample 3
Input
256 12 1444
Output
866273184
Output the remainder of the answer when divided by $10^9+7$
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。