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