#P0132. 台阶问题Ⅱ

台阶问题Ⅱ

台阶问题

题目描述

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

输入格式

两个正整数 N,KN,K

输出格式

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

样例 #1

样例输入 #1

5 2

样例输出 #1

8

提示

  • 对于 20%20\% 的数据,1N101\leq N\leq101K31\leq K\leq3
  • 对于 40%40\% 的数据,1N10001\leq N\leq1000
  • 对于 100%100\% 的数据,1N1000001\leq N\leq1000001K1001\leq K\leq100