Những Viên Ngọc Ma Thuật

Xếp một hàng gồm một số hữu hạn viên ngọc; số viên không được cho trước. Mỗi viên được chọn ở đúng một trong hai dạng:

• dạng thường chiếm $1$ đơn vị độ dài;
• dạng mở rộng chiếm $m$ đơn vị độ dài.

Một cấu hình được xác định bởi thứ tự các dạng viên trong hàng. Vì vậy, chẳng hạn, một viên thường rồi một viên mở rộng khác với một viên mở rộng rồi một viên thường.

Hãy đếm số cấu hình có tổng độ dài đúng bằng $n$.

Input

• Input gồm hai số nguyên $n$ và $m$.

Output

• In số cấu hình theo modulo $1000000007$.

Constraints

• $1\le n\le 10^{18}$.
• $2\le m\le 100$.

Scoring

• Subtask $1$ ($50\%$): $n\le 10^6$.
• Subtask $2$ ($50\%$): không có giới hạn bổ sung.

Example

4 3

3