#include<stdio.h>

#define NMAX 15000000
#define MOD 1048576

int n, res;

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

void solve()
{
	int i, l1 = 12, l2 = 6, l3 = 2, a;
	
	if(n == 1)
		res = 1;		
	else if(n == 2)
		res = 2;
	else if(n == 3)
		res = 6;
	else if(n == 4)
		res = 12;
	else
	{
		for(i = 5; i <= n; i++)
			a = l1 + l3 + 2 * (i - 2), a %= MOD, l3 = l2, l2 = l1, l1 = a;
		res = a;
	}
}

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

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