Description

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

Format

Input

两个正整数N，K。

Output

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

Samples

5 2

8

Limitation

1s, 1024KiB for each test case.