Revenge of the Round Table

Two countries A and B have decided to hold a meeting to get acquainted. In total, n ambassadors from A and B will attend the meeting.

A round table is prepared for the meeting. The ambassadors are being seated at the round table, but they have agreed that, for deeper exchange, more than k ambassadors from the same country will not sit in a row.

Your task is to write a program that reports the number of possible arrangements when rotations are not counted as different. Your program should report that number modulo M = 1000003.

Here is an example. Suppose n = 4 and k = 2. When rotations are counted as different arrangements, the following six arrangements are possible.

AABB
ABBA
BBAA
BAAB
ABAB
BABA

However, when rotations are regarded as the same, the following two arrangements are possible.

AABB
ABAB

Therefore the program should report 2.

The input consists of multiple datasets. Each dataset consists of two integers n (1 ≤ n ≤ 1000) and k (1 ≤ k ≤ 1000) on one line.

It does not always hold that k < n. This means the program should consider cases in which ambassadors from only one country attend the meeting.

The last dataset is followed by a line containing two zeros. This line is not part of any dataset and should not be processed.

For each dataset, print the number of possible arrangements modulo M = 1000003 on one line.