#include <bits/stdc++.h>

using namespace std;

int A[4],n;

ifstream fin("12perm.in");
ofstream fout("12perm.out");

int main(){
	int k=0;
	fin>>n;
	A[1]=2;
	A[2]=6;
	A[3]=12;
	if(n==1)fout<<1;
	else if(n<=4)fout<<A[n-1];
	else{
		for(int i=5;i<=n;i++){
			k=(A[1]+A[3]+2*(i-2))%1048576;
			A[3]=A[2];
			A[2]=A[1];
			A[1]=k;
		}
		fout<<k;
	}
}