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

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main{
	
	String INPUT = "./data/judge/201709/A2164.txt";
	
	public static void main(String[] args) throws IOException {
		new Main().run();
	}
	
	static final int MOD = 1000003;
	static final int MAX_N = 1000 + 16;
	
	
	long[] inv = new long[MAX_N];
	int[][] dp_a = new int[MAX_N][MAX_N];
	int[][] dp_b = new int[MAX_N][MAX_N];
	int[] dp = new int[MAX_N];
	
	void init_inverse(){
		inv[1] = 1;
		for (int i = 2; i < MAX_N; ++i){
			inv[i] = (MOD - (MOD / i) * inv[MOD % i] % MOD) % MOD; 
		}
	}
	
	class GCD{
		int d;
		int x;
		int y;
		public GCD(int d, int x, int y){
			this.d = d;
			this.x = x;
			this.y = y;
		}
	}
	
	GCD extgcd(int a, int b){
		if (b == 0){
			return new GCD(a, 1, 0);
		}
		else{
			GCD p   = extgcd(b, a % b);
			GCD ans = new GCD(0, 0, 0);
			ans.d = p.d;
			ans.x = p.y;
			ans.y = p.x - (a / b) * p.y;
			return ans;
		}
	}
	
	long mod_inverse(int a, int m){
		GCD p = extgcd(a, m);
		if (p.d != 1) return -1;
		return (p.x % m + m) % m;
	}
	
	void DP()
	{
		dp_a = new int[MAX_N][MAX_N];
		dp_b = new int[MAX_N][MAX_N];
		dp   = new int[MAX_N];
		
		int a_sum = 1;
		int b_sum = 0;
		if (K >= N)
	    {
	        K = N - 1;
	        all = 2;
	    }
		
	    dp_a[1][1] = 1;
	    dp_b[1][1] = 0;
	 
	    for (int i = 2; i <= N; i++)
	    {
	        dp_a[i][1] = b_sum; // ??\B?????´??\A????°????????????´?????????A
	        dp_b[i][1] = a_sum; // ??\A?????´??\A????°????????????´?????????B
	        
	        int sum = a_sum + b_sum;
	        a_sum = sum - a_sum;
	        b_sum = sum - a_sum;
	        for (int j = 2; j <= K; j++)
	        {
	            dp_a[i][j] = dp_a[i - 1][j - 1];        // ??¨????°???????A
	            a_sum = (a_sum + dp_a[i][j]) % MOD;
	            dp_b[i][j] = dp_b[i - 1][j - 1];        // ??¨????°???????B
	            b_sum = (b_sum + dp_b[i][j]) % MOD;
	        }
	    }
	 
	    // ???????????????dp_b[i][1~k]??????????¶?dp[i]?????????????°???????????°????????????????????????????????¶????k
	    for (int i = 1; i <= N; i++)
	    {
	        for (int j = 1; j <= K; j++)
	        {
	            dp[i] += dp_b[i][j];
	            dp[i] %= MOD;
	        }
	    }
	 
	    // ????????\A?????´?????????????°?dp_b??????????±??????\
	    for (int i = 1; i <= N; i++)
	    {
	        for (int j = 1; j < K; j++)
	        {
	            dp_b[i][j + 1] += dp_b[i][j];
	            dp_b[i][j + 1] %= MOD;
	        }
	    }
	 
	    // ???????????¢???p???A?????£???????°????A???????¶????k-p?????????dp_b[i-p][0~k-p]???????????????
	    for (int i = 1; i <= N; i++)
	    {
	        for (int p = 1; p <= Math.min(i, K); p++)
	        {
	            dp[i] += dp_b[i - p][K - p];
	            dp[i] %= MOD;
	        }
	    }
	}
	
	int gcd(int a, int b){
		if (b == 0) return a;
		else return gcd(b, a % b);
	}
	
	int N;
	int K;
	
	long ans;
	long all;
	void solve() {
		
		init_inverse();
		
		while (true){
			N = ni();
			K = ni();
			
			if (N + K == 0) break;
			
			ans = 0;
			all = 0;
			
			DP();
			
			for (int i = 0; i < N; ++i){
				ans += 2 * dp[gcd(i, N)];
				ans %= MOD;
			}
			ans = (ans * inv[N]) % MOD;
			out.println(ans + all);
		}
	}

	FastScanner in;
	PrintWriter out;
	
	void run() throws IOException {
		boolean oj;
		try {
			oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
		} catch (Exception e) {
			oj = System.getProperty("ONLINE_JUDGE") != null;
		}
		
		InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
		in = new FastScanner(is);
		out = new PrintWriter(System.out);
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if (!oj){
			System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
		}
	}
	
	public boolean more(){
		return in.hasNext();
	}
	
	public int ni(){
		return in.nextInt();
	}
	
	public long nl(){
		return in.nextLong();
	}
	
	public double nd(){
		return in.nextDouble();
	}
	
	public String ns(){
		return in.nextString();
	}
	
	public char nc(){
		return in.nextChar();
	}
	
	class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		boolean hasNext;

		public FastScanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
			hasNext = true;
		}

		public String nextToken() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception e) {
					hasNext = false;
					return "##";
				}
			}
			return st.nextToken();
		}
		
		String next = null;
		public boolean hasNext(){
			next = nextToken();
			return hasNext;
		}

		public int nextInt() {
			if (next == null){
				hasNext();
			}
			String more = next;
			next = null;
			return Integer.parseInt(more);
		}

		public long nextLong() {
			if (next == null){
				hasNext();
			}
			String more = next;
			next = null;
			return Long.parseLong(more);
		}

		public double nextDouble() {
			if (next == null){
				hasNext();
			}
			String more = next;
			next = null;
			return Double.parseDouble(more);
		}
		
		public String nextString(){
			if (next == null){
				hasNext();
			}
			String more = next;
			next = null;
			return more;
		}
		
		public char nextChar(){
			if (next == null){
				hasNext();
			}
			String more = next;
			next = null;
			return more.charAt(0);
		}
	}
}