// Arup Guha
// 11/11/2010
// Solution to 2010 SE Regional Problem I:  Skyline

/* Consider having all arrangements of buildings 1-n and using these to build
* all arrangement of n+1 buildings. We must insert the tallest building (n+1)
* into the previous valid arrangements. In particular, we can insert it in any
* spot. To the left of the spot we must have i buildings that satisfy the recurrence
* and to the other side we must have n-i buildings that do so. Note that since we
* are inserting the tallest building, if both subsequences adhere to the property
* this new sequence will. Thus, we sum f(i)f(n-i) from i = 0 to n to obtain f(n+1).
* This is the recurrence for Catalan numbers. Double checking the simple base cases
* for the specific problem yields that the desired function that solves this problem
* is exactly the Catalan numbers. Implemented below is a straight dynamic programming
* version of calculating the nth Catalan number using the recurrence exactly. */

import java.util.*;
import java.math.*;

public class i {
	
	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		 
		// Solve all the possible instances now.
		long[] catalan = new long[1001];
		catalan[0] = 1;
		catalan[1] = 1;
		catalan[2] = 2;
		
		// Fill these in using the Catalan number recurrence.
		for (int i=3; i<=1000; i++) 
			
			// This is the sum for catalan[i].
			for (int j=0; j<i; j++)
				catalan[i] = (catalan[i] + catalan[j]*catalan[i-1-j])%1000000;
		
		int n = stdin.nextInt();
		while (n != 0) {
			
			System.out.println(catalan[n]);
			
			// Get next input.
			n = stdin.nextInt();
		}		
	}
	
}