#include <stdio.h>
#define consta 1048576
int main()
{int n,a,b,c,d,x,i;
    freopen("12perm.in","r",stdin);
    freopen("12perm.out","w",stdout);
    scanf("%d",&n);
    if(n==1) {printf("1");return 0;}
    else if(n==2) {printf("2");return 0;}
    else if(n==3) { printf("6");return 0;}
    else if(n==4) {printf("12");return 0;}
    else
{a=1;b=2;c=6;d=12;
    for(i=5;i<=n;i++)
    { 
                     x =(d + b +2 * (i-2));
                     if(x>consta) x%=consta;
     a=b;
     b=c;
     c=d;
     d=x;
     }
     printf("%d",x);
     return 0;
}  
   
}