Ếch ộp


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Có $n+1$ hòn đá được xếp thành một hàng ngang và được đánh số từ $0$ đến $n$ theo hướng từ trái qua phải. Có một chú ếch đang đứng ở hòn đá số 0, ếch muốn nhảy đến hòn đá thứ $n$.

Khi ếch đang đứng ở hòn đá thứ $i$ thì nó có thể nhảy đến hòn đá thứ $j$ với $i<j$ và $j-i\le k$ trong đó $k$ là một số nguyên dương cho trước.

Đếm số cách mà ếch có thể nhảy đến hòn đá thứ $n$.

Dữ liệu

  • Một dòng duy nhất chứa hai số nguyên $n,k \ (0<n<10^{18}; 0<k<100)$.

Kết quả

  • Kết quả bài toán sau khi chia lấy dư cho $10^9+7$.

Ví dụ

Ví dụ 1

input

10 3

output

274

Comments

There are no comments at the moment.