---
tags: 'Propose for Bedao'
---
# CHIA KẸO

<h2>
Statement
</h2>

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.

<b>Yêu cầu:</b> Bạn hãy tính số cách chia kẹo vào túi thỏa mãn nhé.

<h2>
Input
</h2>

- Một dòng chứa ba số nguyên dương $n, m, d$ ($n \le 10^{18}, d\le m \le 10$).

<h2>
Output
</h2>

- 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$.

<h2>
Scoring
</h2>

- Subtask 1 (50 điểm): $n\le 10^5$.
- Subtask 2 (50 điểm): $n\le 10^{18}$.

<h2>
Example
</h2>

| Input | Output |
| ----- | ------ |
| 5 3 1 | 10 |

<h3>
Solution
</h3>

Gọi $f(i,j)$ là số cách chia $i$ kẹo vào các túi sao cho số kẹo ở túi cuối cùng là $j$. $f(i,j)=\sum_{t=j-d}^{j+d}f(i-j,t)$
Từ đây ta ra được thuật toán nhân ma trận.
Code: https://ideone.com/4tLHec