#include <stdio.h>
#define MOD 1048576

int N;

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