No.269 見栄っ張りの募金活動
kmjp問題文最終更新日: 2015-11-14 17:48:39
問題文
学校で募金活動をすることになり、\(N\)人のクラスで\(S\)円を集め寄付することにした。
生徒は出席番号順に寄付金額（０以上の整数）を決めていく。
このクラスの生徒は皆見栄っ張りであり、出席番号順が１つ前の生徒に比べて\(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
入力
3 10 1
出力
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もしくは右上の雲マークをクリックしてアカウントを作成してください。