원탁의 복수

두 나라 A와 B가 서로 친해지기 위해 만남을 갖기로 했다. 이 만남에는 A와 B에서 온 대사들이 합쳐서 n명 참석한다.

만남을 위해 원탁이 준비되었다. 대사들이 원탁에 둘러앉는데, 더 깊은 교류를 위해 같은 나라의 대사가 k명을 초과하여 연속으로 앉지 않기로 했다.

여러분의 임무는 회전을 서로 같은 것으로 볼 때 가능한 배치의 수를 구하는 프로그램을 작성하는 것이다. 프로그램은 그 수를 M = 1000003으로 나눈 나머지를 출력해야 한다.

예를 하나 들어 보자. n = 4이고 k = 2라고 하자. 회전을 서로 다른 것으로 볼 때 다음 여섯 가지 배치가 가능하다.

AABB
ABBA
BBAA
BAAB
ABAB
BABA

그러나 회전을 서로 같은 것으로 보면 다음 두 가지 배치가 가능하다.

AABB
ABAB

따라서 프로그램은 2를 출력해야 한다.

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋은 한 줄에 두 정수 n (1 ≤ n ≤ 1000)과 k (1 ≤ k ≤ 1000)로 주어진다.

항상 k < n이 성립하는 것은 아니다. 즉, 한 나라의 대사만 참석하는 경우도 프로그램이 고려해야 한다.

마지막 데이터셋 다음에는 두 개의 0이 있는 줄이 온다. 이 줄은 어떤 데이터셋의 일부도 아니며 처리해서는 안 된다.

각 데이터셋에 대해 가능한 배치의 수를 M = 1000003으로 나눈 나머지를 한 줄에 출력한다.