#include <cstdio>
#define IN "12perm.in"
#define OUT "12perm.out"
#define N_MAX 15000001
#define MOD 1048576
#define FOR(i,a,b) for(int i=a;i<=b;++i)   

int n;

void scan()
{
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d", &n);
}

void solve()
{
	int xx,x,y,z,aux;
	switch(n)
	{
		case 1:{printf("1\n"); return;}
		case 2:{printf("2\n"); return;}
		case 3:{printf("6\n"); return;}
		case 4:{printf("12\n"); return;}
	}		
	xx=3;
	x=2;
	y=6;
	z=12;
	FOR(i,5,n)
	{
		aux=( z+x+2*xx );
		if(aux>10000)
			aux%=MOD;
		x=y;
		y=z;
		++xx;
		z=aux;
	}	
	
	printf("%d\n", z);
}	

int main()
{
	scan();
	solve();
	return 0;
}