#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;
int v[N_MAX];

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

void solve()
{
	v[1]=1;
	v[2]=2;
	v[3]=6;
	v[4]=12;
	FOR(i,5,n)
		v[i]=( v[i-1]+v[i-3]+2*(i-2) )%MOD;
	
	printf("%d\n", v[n]);
}	

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