#include<stdio.h>
#define MOD 1048576
#define N 15000000
int nr[N];
int main()
{
    FILE *fin,*fout;
    fin=fopen("12perm.in","r");
    fout=fopen("12perm.out","w");
    int n;
    fscanf(fin,"%d",&n);
    nr[0]=1,nr[1]=2,nr[2]=6,nr[3]=12;
    int i;
    for(i=4;i<n;i++)
        nr[i]=(nr[i-3]+nr[i-1]+2*i-4)%MOD;
    fprintf(fout,"%d",nr[n-1]);
    return 0;
}