Competitions

# Dynamic programming - linear

# Grasshopper

Grasshopper lives in the teacher's room. It likes to jump on one dimensional checkerboard. The length of the board is **n** cells. To its regret, it can jump only on **1**, **2**, ..., **k** cells forward.

Once teachers wondered in how many ways a grasshopper can reach the last cell from the first one. Help them to answer this question.

#### Input

Two integers **n** and **k** (**1** ≤ **n** ≤ **30**, **1** ≤ **k** ≤ **10**).

#### Output

Print the number of ways for grasshopper to leap from the first cell to the last.

Input example #1

8 2

Output example #1

21

Input example #2

1 10

Output example #2

1

Input example #4

1 1

Output example #4

1

Input example #8

30 10

Output example #8

265816832