#include <stdio.h>
#include <string.h>

#define MOD 1048576//(1<<20)-1

int main()
{
	int n, i;
	int a1 = 2, a2 = 6, a3 = 12, a4 = 0;
	//int size = 5*sizeof(int);
	freopen("12perm.in", "r", stdin);
	freopen("12perm.out", "w", stdout);

	scanf("%d\n", &n);

	for(i = 5; i <= n; ++i)
	{
		a4 = a3 + a1 + 2*(i-2);

		if(a4 >= MOD)
			a4 %= MOD;

		a1 = a2;
		a2 = a3;
		a3 = a4;
	}

	if(n > 4)
		printf("%d\n", a4 % MOD);
	else if(n == 1)
		printf("1\n");
	else if(n == 2)
		printf("2\n");
	else if(n == 3)
		printf("6\n");
	else if(n == 4)
		printf("12\n");

	fclose(stdin);
	fclose(stdout);

	return 0;
}