Two contries A and B have decided to make a meeting to get acquainted with each other. n ambassadors from A and B will attend the meeting in total.

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

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

Let us provide 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 same, the following two arrangements are possible.


AABB
ABAB


Therefore the program should report 2.



Input

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

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

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

Output

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

Example

Input

3 1
3 2
3 3
4 2
10 5
1000 500
0 0


Output

0
2
4
2
90
570682
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class t>
using table = vector<vector<t>>;
const ld eps = 1e-9;



const int mod = 1000003;
struct Mod {
public:
	int num;
	Mod() : Mod(0) { ; }
	Mod(long long int n) : num((n % mod + mod) % mod) {
		static_assert(mod<INT_MAX / 2, "mod is too big, please make num 'long long int' from 'int'");
	}
	Mod(int n) : Mod(static_cast<long long int>(n)) { ; }
	operator int() { return num; }
};

Mod operator+(const Mod a, const Mod b) { return Mod((a.num + b.num) % mod); }
Mod operator+(const long long int a, const Mod b) { return Mod(a) + b; }
Mod operator+(const Mod a, const long long int  b) { return b + a; }
Mod operator++(Mod &a) { return a + Mod(1); }
Mod operator-(const Mod a, const Mod b) { return Mod((mod + a.num - b.num) % mod); }
Mod operator-(const long long int a, const Mod b) { return Mod(a) - b; }
Mod operator--(Mod &a) { return a - Mod(1); }
Mod operator*(const Mod a, const Mod b) { return Mod(((long long)a.num * b.num) % mod); }
Mod operator*(const long long int a, const Mod b) { return Mod(a)*b; }
Mod operator*(const Mod a, const long long int b) { return Mod(b)*a; }
Mod operator*(const Mod a, const int b) { return Mod(b)*a; }
Mod operator+=(Mod &a, const Mod b) { return a = a + b; }
Mod operator+=(long long int &a, const Mod b) { return a = a + b; }
Mod operator-=(Mod &a, const Mod b) { return a = a - b; }
Mod operator-=(long long int &a, const Mod b) { return a = a - b; }
Mod operator*=(Mod &a, const Mod b) { return a = a * b; }
Mod operator*=(long long int &a, const Mod b) { return a = a * b; }
Mod operator*=(Mod& a, const long long int &b) { return a = a * b; }
Mod operator^(const Mod a, const int n) {
	if (n == 0) return Mod(1);
	Mod res = (a * a) ^ (n / 2);
	if (n % 2) res = res * a;
	return res;
}
Mod mod_pow(const Mod a, const long long  int n) {
	if (n == 0) return Mod(1);
	Mod res = mod_pow((a * a), (n / 2));
	if (n % 2) res = res * a;
	return res;
}
Mod inv(const Mod a) { return a ^ (mod - 2); }
Mod operator/(const Mod a, const Mod b) {
	assert(b.num != 0);
	return a * inv(b);
}
Mod operator/(const long long int a, const Mod b) {
	return Mod(a) / b;
}
Mod operator/=(Mod &a, const Mod b) {
	return a = a / b;
}

#define MAX_MOD_N 1024000

Mod fact[MAX_MOD_N], factinv[MAX_MOD_N];
void init(const int amax = MAX_MOD_N) {
	fact[0] = Mod(1); factinv[0] = 1;
	for (int i = 0; i < amax - 1; ++i) {
		fact[i + 1] = fact[i] * Mod(i + 1);
		factinv[i + 1] = factinv[i] / Mod(i + 1);
	}
}
Mod comb(const int a, const int b) {
	return fact[a] * factinv[b] * factinv[a - b];
}
long long int gcd(long long int l, long long int r) {
	assert(l > 0 && r > 0);
	if (l > r)return gcd(r, l);
	else {
		const long long int num = r%l;
		if (num) {
			return gcd(l, num);
		}
		else {
			return l;
		}
	}
}

Mod dp[1002][1002][2];
int main() {
	
	while (1) {
		int N, K; cin >> N >> K;
		if (!N)break;
		for (int i = 0; i < 1002; ++i) {
			for (int j = 0; j < 1002; ++j) {
				for (int k = 0; k < 2; ++k) {
					dp[i][j][k] = 0;
				}
			}
		}
		dp[1][1][0] = 1;
		for (int i = 1; i <= 1000; ++i) {
			for (int j = 1; j <= 1000; ++j) {
				for (int k = 0; k < 2; ++k) {
					if (j + 1 <= K) {
						dp[i + 1][j + 1][k] += dp[i][j][k];
					}
					dp[i + 1][1][!k] += dp[i][j][k];
				}
			}
		}
		Mod ans = 0;
		for (int l = 0; l < N; ++l) {
			int num;
			if (l)num = gcd(l, N);
			else num = N;

			Mod nans = 0;
			for (int i = 0; i < min(num,K); ++i) {
				for (int j = 1; j <= min(num,K-i); ++j) {
					nans += dp[num - i][j][1];
				}
			}
			ans += nans;
		}
		ans *= 2;
		ans /= N;
		if (N <= K)ans += 2;
		cout << ans << endl;

	}
	return 0;
}