#include <stdio.h>

int main()
{
	freopen("12perm.in", "r", stdin);
#ifndef _SCREEN_
	freopen("12perm.out", "w", stdout);
#endif

	int unu = 1, doi = 2, trei = 6, patru = 12, N, i, aux;

	scanf("%d\n", &N);
	if (N == 1) printf("1\n");
	if (N == 2) printf("2\n");
	if (N == 3) printf("6\n");
	if (N == 4) printf("12\n");
	if (N >= 5) {
		for (i = 5; i <= N; i ++) {
			aux = (patru + unu + (2 * (i - 2) % 1048576)) % 1048576;
			unu = doi, doi = trei, trei = patru, patru = aux;
		}
		printf("%d\n", aux);
	}

	return 0;
}