#include <stdio.h>

#define maxn 1010

const int P=12345;

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

void run(void)
{
	int i;
	f[1][0]=9;
	f[1][1]=1;
	for (i=2;i<n;i++)
	{
		f[i][0]=(f[i-1][1]+f[i-1][0]*9)%P;
		f[i][1]=(f[i-1][0]+f[i-1][1]*9)%P;
	}
	if (n!=1)
		f[n][0]=(f[n-1][1]+f[n-1][0]*8)%P;
	ans=f[n][0];
}

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

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