#include<stdio.h>
FILE*f=fopen("12perm.in","r");
FILE*g=fopen("12perm.out","w");
int main()
 {
 int n,i,a,b,c,d;
 fscanf(f,"%d",&n);
 if(n==1) fprintf(g,"1\n");
 else if (n==2) fprintf(g,"2\n");
 else if(n==3) fprintf(g,"6\n");
 else if(n==4) fprintf(g,"12\n");
 else
  {
  a=2;
  b=6;
  c=12;
  for(i=5;i<=n;++i)
      {
      d=a+c+2*(i-2);
      while(d>=1048576) d-=1048576;
      a=b;
      b=c;
      c=d;

      }
  fprintf(g,"%d\n",d);

  }
return 0;
}