#include<cstdio>
#define mod 1048576
using namespace std;
int main(){
    freopen("12perm.in","r",stdin);
    freopen("12perm.out","w",stdout);
    int n,i,a=1,b=2,c=6,d=12,e,p=6;
    scanf("%d",&n);
    if(n==1){
        printf("%d",a);
        return 0;
    }
    if(n==2){
        printf("%d",b);
        return 0;
    }
    if(n==3){
        printf("%d",c);
        return 0;
    }
    if(n==4){
        printf("%d",d);
        return 0;
    }
    for(i=5;i<=n;i++){
        e=(b+d+p)%mod;
        a=b;
        b=c;
        c=d;
        d=e;
        p+=2;
    }
    printf("%d",e);
    return 0;
}