/*#include<cstdio>
#include<algorithm>
using namespace std;
#define mod 1000000
int main(){
    int n,i,j,k,sum,s[1010],f;
    //while(scanf("%d",&n))
    for(n=3;n<=20;n++){
        if(n==0)break;
        for(i=1;i<=n;i++)
            s[i]=i;
        sum=0;
        do{
            f=1;
            for(i=1;i<=n && f;i++)
                for(j=i+1;j<=n && f;j++)
                    for(k=j+1;k<=n && f;k++){
                        if(s[i]<s[j] && s[j]<s[k]){
                            f=0;
                            break;
                        }
                    }
            if(f)sum++;
        }while(next_permutation(s+1,s+n+1));
        printf(" %d =  %d\n",n,sum);
    }
}*/
#include<cstdio>
#define mod 1000000
long long h[1010];
int main(){
    int n,i,j;
    h[0]=1;h[1]=1;
    for(i=2;i<=1000;i++){
        for(j=0;j<=i-1;j++)
            h[i]=(h[i]+h[j]*h[i-1-j])%mod;
    }
    while(scanf("%d",&n)){
        if(n==0)break;
        printf("%lld\n",h[n]);
    }
}