#include<stdio.h>

#define NMAX 15000000
#define MOD 1048576

int n, res, v[ NMAX ];

void read()
{
	FILE *f = fopen("12perm.in", "r");
	
	fscanf(f, "%d", &n);
	
	fclose(f);
}

void solve()
{
	int i;
	
	v[1] = 1, v[2] = 2, v[3] = 6, v[4] = 12;
	for(i = 5; i <= n; i++)
		v[i] = ( v[i-1] + v[i-3] + 2 * (i - 2) ) % MOD;
	res = v[n];
}

void write()
{
	FILE *g = fopen("12perm.out", "w");
	
	fprintf(g, "%d\n", res);
	
	fclose(g);
}

int main()
{
	read();
	solve();
	write();
	return 0;
}