계단 오르기 2

문제

서현이는 $N$개로 이루어진 계단을 올라야 한다. 서현이는 다음 규칙을 만족하며 계단을 오르려고 한다.

• 한 번에 한 계단씩 혹은 두 계단씩 혹은 $\cdots$ 혹은 $K$ 계단씩 오를 수 있다.
• 마지막 계단은 반드시 밟아야 한다.

서현이가 계단을 오르는 경우의 수를 $1\,000$으로 나눈 나머지를 구해보자.

입력

첫째 줄에 $N$과 $K$가 공백으로 구분되어 주어진다. ($2\le K\le N\le 1\,000$)

출력

서현이가 계단을 오르는 경우의 수를 $1\,000$으로 나눈 나머지를 출력한다.

예제 입력 1

5 1

예제 출력 1

1

예제 입력 2

5 2

예제 출력 2

8

예제 입력 3

5 3

예제 출력 3

13

예제 입력 4

5 4

예제 출력 4

15

예제 입력 5

5 5

예제 출력 5

16

예제 입력 6

1000 1000

예제 출력 6

688