#include <stdio.h>

FILE *f = fopen("12perm.in","rt"), *g = fopen("12perm.out","wt");

long long sol,i,j,n,a,b,c;


void solve()
{
for (i=5;i<=n;i++)
   {sol=a+c+2*(i-2);
   while (sol>1048576)
	sol-=1048576;
   c=b;
   b=a;
   a=sol;
   }
fprintf(g,"%lld",sol);
}

int main()
{
fscanf(f,"%lld",&n);
if (n==1) {fprintf(g,"1");return 0;}
if (n==2) {fprintf(g,"2");return 0;}
if (n==3) {fprintf(g,"6");return 0;}
if (n==4) {fprintf(g,"12");return 0;}
a=12;b=6;c=2;
solve();
fclose(f);
fclose(g);
return 0;
}