Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Кузнечик-KMax

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего. Требуется найти количество способов, которыми Кузнечик может добраться до столбика с номером N . Учитывайте, что Кузнечик не может прыгать назад.
 
Поскольку количество способов, которое нужно найти, может быть очень велико, вычислите его по модулю 106 + 7 , то есть найдите остаток от деления этого числа на 10 6 + 7 .
 
Входные данные
Входная строка содержит натуральные числа N и K , разделённые пробелом. Гарантируется, что 1 ≤ N , K ≤ 10000 .
 
Выходные данные
Программа должна вывести одно число: количество способов, которыми Кузнечик может добраться до столбика с номером N , вычисленное по модулю 106 + 7 .

Ввод Вывод
10 5 236
100 50 934384

 


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: