Task
Time limit:
1000 ms,
Memory limit:
256 Mb
Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего. Требуется найти количество способов, которыми Кузнечик может добраться до столбика с номером N . Учитывайте, что Кузнечик не может прыгать назад.
Поскольку количество способов, которое нужно найти, может быть очень велико, вычислите его по модулю 106 + 7 , то есть найдите остаток от деления этого числа на 10 6 + 7 .
Входные данные
Входная строка содержит натуральные числа N и K , разделённые пробелом. Гарантируется, что 1 ≤ N , K ≤ 10000 .
Выходные данные
Программа должна вывести одно число: количество способов, которыми Кузнечик может добраться до столбика с номером N , вычисленное по модулю 10
6 + 7 .
|
Ввод |
Вывод |
|
10 5 |
236 |
|
100 50 |
934384 |