该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

有N级的台阶，你一开始在底部，每次可以向上迈最多K级台阶（最少1级），问到达第N级台阶有多少种不同方式

Format

Input

两个正整数N，K。

Output

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

Samples

5 2

8

Limitation

1s, 1024KiB for each test case.