#include <stdio.h>

#define ALA 1048576
#define NMAX 15000000

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

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

 scanf("%ld",&N);
 R1=1; R2=2; R3=6; R4=12;
 for (i=5;i<=N;i++)
    {
     R4=(R1 + R3 + 2*(i-2))%ALA;
     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("%ld",R4+1);

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