No.1011 Infinite Stairs

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 158
作問者 : otamay6otamay6 / テスター : Lemma299Lemma299
16 ProblemId : 3663 / 出題時の順位表
問題文最終更新日: 2020-03-13 21:03:59

問題文

無限に続く階段があります。あなたは最初 $0$ 段目にいて、次の行動を $N$ 回繰り返そうとしています。
・$i$ 段目にいるとき、 $i+1$ 段目, $i+2$ 段目, $\dots$ , $i+d$ 段目のいずれかに移動する
$N$ 回の移動のあと、$K$ 段目に辿りつく移動方法が何通りあるかを求めて下さい。
ただし答えは非常に大きくなることがあるので $10^9+7$ で割った余りを求めて下さい

入力

$N\ d\ K$

入力は全て整数で与えられる
$1 \le N,d \le 300$
$N \le K \le d \times N$

出力

$N$ 回の移動のあと、$K$ 段目に辿りつく移動方法が何通りあるかを出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3 2 5
出力
3

(2,2,1), (2,1,2), (1,2,2) の3通りの移動方法があります

サンプル2
入力
6 3 10
出力
90

ありえる移動方法のうち昇順なものは (1,1,1,1,3,3), (1,1,1,2,2,3), (1,1,2,2,2,2) の3通りで、このうちどれかを並び替えたものは
${}_{6}{\rm C}_{2}$ + ${}_{6}{\rm C}_{3}\times {}_{3}{\rm C}_{2}$ + ${}_{6}{\rm C}_{2}$ = 90 通りあります

サンプル3
入力
256 12 1444
出力
866273184

答えは $10^9+7$ で割った余りを出力してください

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。