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

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.