P1192 Staircase Problem

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?

Two positive integers $N,K$.

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

- 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