#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;
	if(n<5)
	{
		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 )%MOD;
		x=y;
		y=z;
		++xx;
		z=aux;
	}	
	
	printf("%d\n", z);
}	

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