#include <stdio.h>

int N,R1,R2,R3,i,R4;

int main()
{
 freopen("12perm.in","r",stdin);
 freopen("12perm.out","w",stdout);

 scanf("%d",&N);
 R1=2; R2=6; R3=12;
 for (i=5;i<=N;i++)
    {
     R4=((R1 + R3 + 2*(i-2)) % 1048576);
     R1=R2; R2=R3; R3=R4;
    }

 if (N==1)
   printf("1");
   else
 if (N==2)
   printf("2");
   else
 if (N==3)
   printf("6");
   else
 if (N==4)
   printf("12");
   else
 printf("%d",R4);

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