Question

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего. Требуется найти количество способов, которыми Кузнечик может добраться до столбика с номером N . Учитывайте, что Кузнечик не может прыгать назад.

Входные данные

Входная строка содержит натуральные числа N и K , разделённые пробелом. Гарантируется, что 1 ≤ N , K ≤ 32 .


Выходные данные

Программа должна вывести одно число: количество способов, которыми Кузнечик может добраться до столбика с номером N .


Примеры
Входные данные
5 4
Выходные данные
8
Программа должна быть на питоне

Answer 1

n=int(input())

k=int(input())

a=[1]

for i in range(1,n):

 for j in range(i-1,i-k-1,-1):

   if j<0 :

     break

   a.append(0)

   a[i]+=a[j]

print(a[n-1])