#include <cstdio>
#define MOD 1048576

using namespace std;

long long N;

int main() {
	int a, b, c, t;
	long long i;
	freopen("12perm.in", "r", stdin);
	freopen("12perm.out", "w", stdout);
	
	scanf("%lld\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)%MOD;
		a=b;
		b=c;
		c=t;
	}
	
	printf("%d\n", a);
	
	return 0;
}