//12-perm
#include <stdio.h>
#define INPUT "12perm.in"
#define OUTPUT "12perm.out"
#define CONST 1048576
int N;
int main()
{
	freopen(INPUT, "r", stdin);
	scanf("%d", &N);
	int i, i_3 = 2, i_2 = 6, i_1 = 12;
	int nr = 0;
	switch(N)
	{
		case 1:nr = 1;break;
		case 2:nr = 2;break;
		case 3:nr = 6;break;
		case 4:nr =12;break;
		default:
			for(i = 5; i <= N; ++i)
				nr = (i_3 + i_1 + 2*(i-2)) % CONST,
				i_3 = i_2, i_2 = i_1, i_1 = nr;
	}
	freopen(OUTPUT, "w"m stdout);
	printf("%d\n", nr);
	return 0;
}