题目描述

小明要爬一个有 $N$ 级台阶的楼梯。他一开始站在地面（第 $0$ 级），每次可以向上迈 $1$ 到 $K$ 级台阶。请问小明到达第 $N$ 级台阶共有多少种不同的走法？答案对 $100003$ 取模。

输入格式

一行两个正整数 $N$ 和 $K$。

输出格式

一个正整数，表示到达第 $N$ 级台阶的不同走法数，结果对 $100003$ 取模。

样例

5 2

8

提示

• 对于 $20\%$ 的数据，$1\leq N\leq10$，$1\leq K\leq3$；
• 对于 $40\%$ 的数据，$1\leq N\leq1000$；
• 对于 $100\%$ 的数据，$1\leq N\leq10^5$，$1\leq K\leq100$。