说明

假设你正在爬楼梯。需要 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