#795. 台阶问题

台阶问题

台阶问题

题目描述

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

输入格式

两个正整数N,K。

输出格式

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

样例 #1

样例输入 #1

5 2

样例输出 #1

8

提示

对于20%20\%的数据,有N10,K3N ≤ 10, K ≤ 3;

对于40%40\%的数据,有N1000N ≤ 1000;

对于100%100\%的数据,有N100000,K100N ≤ 100000,K ≤ 100