#include<stdio.h>
main()
{
long n,a=2,b=6,c=12,d,k=5,x,valid,div=1048576;
freopen("12perm.in","r",stdin);
freopen("12perm.out","w",stdout);
fscanf(stdin,"%ld",&n);
if(n==1) { x=1;
	   fprintf(stdout,"%ld",x); }
if(n==2) { x=2;
	   fprintf(stdout,"%ld",x); }
if(n==3) { x=6;
	   fprintf(stdout,"%ld",x); }
if(n==4) { x=12;
	   fprintf(stdout,"%ld",x); }
if(n>4)
{
  do{
     d=2*(k-2);d+=a;d+=c;
     d%=div;
     a=b;b=c;c=d;
     k++;
     }while(k<=n);
  fprintf(stdout,"%ld",d);
}


fclose(stdin);
fclose(stdout);
return 0;
}