台阶问题

题目描述

有$N$级的台阶，你一开始在底部，每次可以向上迈最多$K$级台阶（最少$1$级），问到达第$N$级台阶有多少种不同方式。

输入格式

两个正整数N，K。

输出格式

一个正整数，为不同方式数，由于答案可能很大，你需要输出$ans \bmod 100003$后的结果。

样例 #1

样例输入 #1

5 2

样例输出 #1

8

样例 #2

样例输入 #2

82153 64

样例输出 #2

87409

提示

对于$20\%$的数据,有$N ≤ 10, K ≤ 3$;

对于$40\%$的数据，有$N ≤ 1000$;

对于$100\%$的数据，有$N ≤ 100000,K ≤ 100$。