5785: 【系列题】爬楼梯(二)

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:110 Solved:20

Description

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

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

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

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

Input

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


Output

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

Sample Input Copy

3 3

Sample Output Copy

4

HINT

样例说明:

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

1、1 + 1 + 1

2、1 + 2

3、2 + 1

4、3

数据范围:

1 <= n <= 1000

1 <= k <= 10