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

输入格式

两个正整数 $N,K$。

输出格式

一个正整数 $ans\pmod{100003}$，为到达第 $N$ 级台阶的不同方式数。

样例 1

输入：

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$。

本站计分说明

本站按原题给出的数据比例重建正式测试点，各测试点等权，总分为 100 分；按通过的测试点累加得分。

来源：Luogu_P1192。本站使用重新构建的测试数据。