#include<fstream>
#define dim 15000007
#define mod 1048576
using namespace std;


ifstream f("12perm.in");
ofstream g("12perm.out");
long  A,B,C,D,n,i;
int main (){
	
	f>>n;
	A= 1, B=2, C= 6, D= 12;
	if(n==1){
		g<<A;
		return 0;
	}
	if(n==2){
		g<<B;
		return 0;
	}
	if(n==3){
		g<<C;
		return 0;
	}
	if(n==4){
		g<<D;
		return 0;
	}
		
		for(i=5;i<=n;++i){
			long aux=D;
			D=(aux+B+2*(i-2))%mod;
			B=C,C=aux;
			
			
		}
		
		g<<D<<"\n";
	
	return 0;
}