No.269 見栄っ張りの募金活動

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 100
作問者 : kmjpkmjp

18 ProblemId : 473 / 出題時の順位表

問題文

学校で募金活動をすることになり、\(N\)人のクラスで\(S\)円を集め寄付することにした。
生徒は出席番号順に寄付金額(0以上の整数)を決めていく。

このクラスの生徒は皆見栄っ張りであり、出席番号順が1つ前の生徒に比べて\(K\)円以上高い金額を寄付しないと気が済まず不満になるようだ。
(最初に金額を決める生徒は比べる相手がいないので何円寄付しても良い。0円でも構わない)

不満な生徒が現れることなく、クラスの合計寄付金額がちょうど\(S\)円となるような各生徒の寄付金額の組み合わせは何通りあるか。
組み合わせ数を\(10^9+7\)で割った余りを答えよ。

入力

\(N\) \(S\) \(K\)

\(N, S, K\)は以下の条件を満たす整数である。
\(2 \le N \le 100\)
\(0 \le S \le 20000\)
\(0 \le K \le 100\)

出力

生徒の寄付金額の組み合わせ数を1行で答えよ。

サンプル

サンプル1
入力
3 10 1
出力
8

3人の寄付金額を出席番号順に並べると以下の8通りである。
- (0, 1, 9), (0, 2, 8), (0, 3, 7), (0, 4, 6)
- (1, 2, 7), (1, 3, 6), (1, 4, 5)
- (2, 3, 5)

サンプル2
入力
20 1000 10
出力
0

皆見栄っ張りなので、合計寄付金額は1000円を容易に超えてしまうようだ。

サンプル3
入力
55 2555 1
出力
966857668

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。