#include <stdio.h>

#define maxn 1010

const int P=12345;

int n,ans,f[maxn];
FILE *f1,*f2;

void run(void)
{
	int i,j,m;
	f[0]=f[1]=1;
	f[2]=2;
	//f[3]=4;
	for (i=3;i<=n;i++)
	{
		m=i-2;
		f[i]=f[i-1];
		for (j=0;j<=m;j++)
			f[i]=(f[i]+(f[j]*f[m-j])%P)%P;
		f[i]%=P;
	}
	ans=f[n]%P;
}

void ini(void)
{
	fscanf(f1,"%d",&n);
}

int main(void)
{
	f1=fopen("circlex.in","r");
	f2=fopen("circlex.out","w");
	ini();
	run();
	fprintf(f2,"%d",ans);
	fclose(f1);fclose(f2);
	return 0;
}