题目描述

一段楼梯共有 $n$ 阶，小明每次可以走 $1$ 阶、$2$ 阶……最多 $k$ 阶（每一步的阶数为不超过 $k$ 的正整数）。请问小明走完这 $n$ 阶楼梯，一共有多少种不同的走法？

两种走法不同，当且仅当其中某一步走的阶数不同。

输入格式

一行两个整数 $n, k$，整数之间以一个空格隔开。

输出格式

一行一个整数，表示走完 $n$ 阶楼梯的不同走法总数。

样例 #1

样例输入 #1

4 2

样例输出 #1

5

样例解释 #1

当 $n=4$，$k=2$ 时，共有如下 5 种走法：

1. $1 + 1 + 1 + 1$
2. $1 + 1 + 2$
3. $1 + 2 + 1$
4. $2 + 1 + 1$
5. $2 + 2$

数据范围与提示

对于 $40\%$ 的数据，$k = 2$；
对于 $70\%$ 的数据，$n \le 20$，$k \le 8$；
对于 $100\%$ 的数据：

• $1 \le n \le 5000$
• $1 \le k \le 10$