e-olymp
Соревнования

January 19,20. One-dimentional Dynamic Programming

Кузнечик

prb4051

У одного из преподавателей в комнате живёт кузнечик, который очень любит прыгать по одномерной клетчатой доске. Длина доски n клеток. К его сожалению, он умеет прыгать только на 1, 2, ..., k клеток вперёд.

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

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

Два целых числа n и k (1n30, 1k10).

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

Выведите количество способов, которыми кузнечик может допрыгать из первой клетки до последней.

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
8 2
Выходные данные #1
21