Ếch ộp
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