Problem Description

There are $N$ steps. You start at the bottom, and each time you can climb $1\sim K$ steps upward. How many different ways are there to reach the $N$-th step?

Input Format

Two positive integers $N,K$.

Output Format

A single positive integer $ans\pmod{100003}$, the number of different ways to reach the $N$-th step.

5 2

8

Hint

• For $20\%$ of the testdata, $1\leq N\leq10$, $1\leq K\leq3$.
• For $40\%$ of the testdata, $1\leq N\leq1000$.
• For $100\%$ of the testdata, $1\leq N\leq100000$, $1\leq K\leq100$.

Translated by ChatGPT 5