Calculating the Number of Ways to Climb Stairs

Fred is trying to climb a staircase with n steps. However, he can climb at most max_step steps in a single move. Your task is to compute the total number of distinct ways Fred can reach the top of the staircase.

The recurrence relation for this problem can be written in \( \LaTeX \) as:

\[ \text{dp}[i] = \sum_{j=1}^{\min(i,\, \text{max\_step})} \text{dp}[i-j], \quad \text{with } \text{dp}[0]=1. \]

For example, when n = 4 and max_step = 2, there are 5 distinct ways to climb to the top.

inputFormat

The input is given via stdin and consists of two space-separated integers:

• n: the number of steps in the staircase (non-negative integer).
• max_step: the maximum number of steps Fred can climb in one move (positive integer).

outputFormat

The output should be printed to stdout and is a single integer representing the total number of distinct ways to climb a staircase of n steps.

## sample

4 2

5