//T[1]=1 ; t[2]=2; t[3]=6; t[4]=12;
//T[i]=t[i-1]+t[i-3]+2*(i-2)
#include<stdio.h>
main()
{
long n,a,b,c,d,i,j,k,m,s,r,t,x,sp,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)
{ a=2;b=6;c=12;
  k=5;
  valid=0;
  do{
     d=2*(k-2);d+=a;d+=c;
     d%=div;
     if(n==k)valid=1;
     else {a=b;b=c;c=d;}
     k++;
     }while(valid==0);
  if(valid==1)fprintf(stdout,"%ld",d);
}


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