台阶问题

题目描述

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

输入输出格式

输入格式


两个正整数 $N,K$。

输出格式


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

输入输出样例

输入样例 #1

5 2

输出样例 #1

8

说明

- 对于 $20\%$ 的数据,$1\leq N\leq10$,$1\leq K\leq3$; - 对于 $40\%$ 的数据,$1\leq N\leq1000$; - 对于 $100\%$ 的数据,$1\leq N\leq100000$,$1\leq K\leq100$。