#include <stdio.h>

long n,i,a,b,c,d;

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