Bedao Mini Contest 22 - Chia kẹo

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

Please read the guidelines before commenting.