该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

小糖原本是一名技术高超的爬楼梯高手，凭借着高级的走位，哪怕是五人一组的爬楼梯小组比赛，也凭借着四保一的配合方式打出了不小的成绩，但是后来因为某种原因（一直没能拿到冠军）退役了，如今小糖重返赛场，你能否帮助小糖拿到冠军呢！

题目描述

小糖有高超的爬楼梯走位，他可以选择一步爬一级、两级、三级...... k 级台阶，编一个程序，帮一开始在台阶底部的小糖计算一下，每次可以向上迈 1∼k 级台阶，到达第 n 级台阶有多少种不同的方式。

输入

一行两个整数 n 和 k ，表示要到达第 n 级台阶,且一次最多只能爬 k 级台阶。

输出

一个整数ans，代表到达第 n 级台阶有多少种不同的方式，由于数据可能很大，对答案取1003的模。
（相当于求ans%1003）

样例

2 1

1

3 3

4

4 2

5

样例解释

-对于第一个样例，小糖要到达二级台阶，因为一次最多只能爬一级台阶，所以只有一级一级地往上爬这1种方法；
-对于样例二，小糖可以选择3或者1 1 1或者1 2以及2 1这4种爬法到达第三级台阶；
-对于样例三，小糖可以选择1 1 1 1或者1 2 1或者2 1 1或者1 1 2以及2 2这5种方法到达第四级台阶。

数据范围

1≤n≤100000
1≤k≤100