#include <stdio.h>

const int MOD = 1048576;
int N, A, B, C, D;

int main ()
{
	freopen ("12perm.in", "r", stdin);
	freopen ("12perm.out", "w", stdout);
	
	scanf ("%d", &N);
	A = 1, B = 2, C = 6, D = 12;
	
	for (int i = 2; i <= N; i++)
	{ 
		A = B, B = C, C = D;
		D = A + C + ((i+1)<<1);
		if (D >= MOD) D -= MOD;
	}
	
	printf ("%d\n", A);
	return 0;
}