台阶问题

题目描述

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

输入输出格式

输入格式


两个正整数N,K。

输出格式


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

输入输出样例

输入样例 #1

5 2

输出样例 #1

8

说明

对于$20\%$的数据,有$N ≤ 10, K ≤ 3$; 对于$40\%$的数据,有$N ≤ 1000$; 对于$100\%$的数据,有$N ≤ 100000,K ≤ 100$。