No.269 The Show-Offs' Fundraiser
kmjpProblem Statement
A school is holding a fundraising campaign, and a class of \(N\) students has decided to collect and donate \(S\) yen.
The students decide their donation amounts (integers of at least 0) in order of their student numbers.
All the students in this class are show-offs: each student becomes dissatisfied unless they donate at least \(K\) yen more than the student immediately before them in student-number order.
(The student who decides first has no one to compare with, so they may donate any amount. Even 0 yen is fine.)
How many combinations of donation amounts of the students are there such that no student becomes dissatisfied and the total donation of the class is exactly \(S\) yen?
Output the number of combinations modulo \(10^9+7\).
Input
\(N\) \(S\) \(K\)
\(N, S, K\) are integers satisfying the following conditions.
\(2 \le N \le 100\)
\(0 \le S \le 20000\)
\(0 \le K \le 100\)
Output
Output the number of combinations of the students' donation amounts on one line.
Sample
Sample 1
Input
3 10 1
Output
8
Listing the donation amounts of the three students in order of student number, there are the following 8 combinations.
- (0, 1, 9), (0, 2, 8), (0, 3, 7), (0, 4, 6)
- (1, 2, 7), (1, 3, 6), (1, 4, 5)
- (2, 3, 5)
Sample 2
Input
20 1000 10
Output
0
Since everyone is a show-off, the total donation easily exceeds 1000 yen.
Sample 3
Input
55 2555 1
Output
966857668
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。