Description

LCL同学渐渐坠入梦乡...

他梦见自己来到了一个很长很长的阶梯前面...

已知LCL眼前有N级台阶，他每次最多可以迈上K级台阶，求他到顶端有多少种方案

Input Format

两个正整数N，K。

Output Format

一个正整数，为不同方式数，由于答案可能很大，你需要输出$ans\mod100003$后的结果。

5 2​

8​

Hint

dfs是过不了的

Source

递归