Problem
Châu chấu nhảy trên các cột nằm trên cùng một đường thẳng với khoảng cách bằng nhau. Các cột có số thứ tự từ 1 đến N . Lúc đầu, Châu chấu ngồi trên cột có số 1. Nó có thể chuyển tiếp từ các thanh 1 sang K, tính từ thanh hiện tại. Yêu cầu tìm số cách mà Grasshopper có thể đến cột có số N. Hãy nhớ rằng Châu chấu không thể nhảy lùi.
Vì số cách tìm có thể rất lớn, nên modulo \(10^6 + 7\) , tức là tìm phần còn lại của phép chia số này cho \(10^6 + 7\) .
Input: Chuỗi đầu vào chứa các số tự nhiên N và K cách nhau bởi dấu cách. Đảm bảo rằng \(1 <= N ,\ K <= 10000\).
Đầu ra: Chương trình sẽ in ra một số duy nhất: số cách Châu chấu có thể đi đến cột được đánh số N được tính toán từ mô-đun \(10^6+7\).
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
10 5 |
236 |
| 2 |
100 50 |
934384 |