#include <stdio.h>

FILE *f,*s;

int n;

int main()
{
	f=fopen("12perm.in","r");
	s=fopen("12perm.out","w");
	
	fscanf(f,"%d",&n);
	
	int a=2;
	int b=6;
	int c=12;
	
	int d;
	
	for(int i=5;i<=n;++i)
	{
		d=c+a+2*(i-2);
		
		while(d>=1048576)
			d-=1048576;
		
		a=b;
		b=c;
		c=d;
	}	
	
	if(n==2)
		fprintf(s,"2");
	
	if(n==3)
		fprintf(s,"6");
	
	if(n==4)
		fprintf(s,"12");
	
	if(n>4)
		fprintf(s,"%d",d);
	
	fclose(s);
	
	return 0;
}