#1197. 【系列题】爬楼梯(二)

【系列题】爬楼梯(二)

说明

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 到 k 个台阶。你有多少种不同的方法可以爬到楼顶呢?

因为答案会很大,因此请将答案取模1000后输出

本题为爬楼梯进阶班,请先完成【系列题】爬楼梯(一)

输入格式

一行两个整数n和k,空格隔开


输出格式

一个整数,即爬到第n级台阶的方案数 % 1000后的结果

样例

3 3
4

提示

样例说明:

每次爬1~3级台阶,爬上3级台阶的方案数有4种,分别如下:

1、1 + 1 + 1

2、1 + 2

3、2 + 1

4、3

数据范围:

1 <= n <= 1000

1 <= k <= 10


相关

在以下作业中:

dp