Có ~n~ cái kẹo trên bàn; người ta muốn cất kẹo vào trong một số túi sao cho mỗi túi chứa một số các viên kẹo nằm liên tiếp nhau trên bàn.
Đồng thời, mỗi túi có không quá ~m~ viên kẹo, và số kẹo trong hai túi liên tiếp hơn kém nhau không quá ~d~ viên.
Yêu cầu: Bạn hãy tính số cách chia kẹo vào túi thỏa mãn nhé. Hai cách chia được coi là khác nhau nếu số túi sử dụng là khác nhau, hoặc tồn tại một túi sao cho trong hai cách, số lượng kẹo tại túi đó khác nhau.
Input
Một dòng chứa ba số nguyên dương ~n, m, d~ (~n \le 10^{18}, d\le m \le 10~).
Output
In ra một số nguyên là số cách chia kẹo. Vì đáp án có thể rất lớn nên hãy in ra số dư khi chia cho ~10^9 + 7~.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~20~ | ~n \le 10^5~ |
2 | ~30~ | ~m = 2~ |
3 | ~50~ | Không có ràng buộc gì thêm |
Sample Input 1
5 3 1
Sample Output 1
10
Notes
Ta có ~10~ cách chia:
(1, 1, 1, 1, 1)
(1, 1, 1, 2)
(1, 1, 2, 1)
(1, 2, 1, 1)
(2, 1, 1, 1)
(1, 2, 2)
(2, 2, 1)
(2, 1, 2)
(2, 3)
(3, 2)
Chú thích: Phần tử thứ ~i~ là số viên kẹo trong túi thứ ~i~ của cách chia.
Comments
:v
This comment is hidden due to too much negative feedback. Show it anyway.