Climbing Stairs

You are given a staircase with \(N\) steps. Initially you are at the bottom (step 0) and you want to reach the \(N\)th step. At each move, you can climb any number of steps from 1 to \(K\) (inclusive). Determine the number of distinct ways to reach exactly the \(N\)th step.

The problem can be modeled using the following recurrence:

[ dp[i] = \sum_{j=1}^{K} dp[i-j] \quad \text{for } i \ge 1 \quad \text{with } dp[0]=1 ]

Note that when \(i - j < 0\), that term is ignored.

inputFormat

The input consists of a single line containing two space-separated integers \(N\) and \(K\), where \(N\) is the number of steps and \(K\) is the maximum number of steps you can climb in one move.

outputFormat

Output a single integer representing the number of ways to reach the \(N\)th step.

sample

3 2

3