#include <cstdio>
#include <cstring>
const int MOD = 1000000;
int cat[1010];
int main()
{
memset(cat,0,sizeof(cat));
int n,i=0,j=0;
cat[0]=1;
for(i=1;i<=1000;i++)
for(j=0;j<=i-1;j++)
cat[i]+=((cat[j]*cat[i-1-j])%MOD);
while(scanf("%d",&n)){if(n==0)break;
printf("%d\n",cat[n]);
}
return 0;
}
