e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Dynamic Programming - Linear

Коник

prb4051

У одного з викладачів у кімнаті живе коник, який дуже полюбляє стрибати по одномерній клітчатій дошці. Довжина дошки n клітинок. На жаль, він вміє стрибати лише на 1, 2, ..., k клітинок уперед.

Однаого разу викладачам стало цікаво, скількома способами коник може дострибати з першої клітинки до останньої. Допоможіть їм відповісти на це питання.

Вхідні дані

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

Вихідні дані

Виведіть кількість способів, якими коник зможе дострибати з першої клітинки до останньої.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
8 2
Вихідні дані #1
21
Вхідні дані #2
1 10
Вихідні дані #2
1
Вхідні дані #4
1 1
Вихідні дані #4
1