問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 389
作問者 : 👑 kmjpkmjp
40 ProblemId : 473 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:48:39

問題文

学校で募金活動をすることになり、\(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

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