Problem
Belalang melompat pada lajur yang terletak pada garisan yang sama pada jarak yang sama antara satu sama lain. Lajur mempunyai nombor siri daripada 1 hingga N . Pada mulanya, Grasshopper duduk pada jawatan dengan nombor 1. Ia boleh melompat ke hadapan daripada bar 1 kepada K, mengira daripada bar semasa. Ia diperlukan untuk mencari bilangan cara di mana Grasshopper boleh sampai ke lajur dengan nombor N. Perlu diingat bahawa Belalang tidak boleh melompat ke belakang.
Memandangkan bilangan cara untuk mencari boleh menjadi sangat besar, modulo \(10^6 + 7\) , iaitu cari baki pembahagian nombor ini kepada \(10^6 + 7\) .
Input: Rentetan input mengandungi nombor asli N dan K yang dipisahkan oleh ruang. Dijamin bahawa \(1 <= N ,\ K <= 10000\).
Output: Atur cara harus mencetak satu nombor: bilangan cara Grasshopper boleh sampai ke lajur bernombor N dikira daripada modul \(10^6+7\).
Contoh
| # |
Input |
Output |
| 1 |
10 5 |
236 |
| 2 |
100 50 |
934384 |