#include<stdio.h>
#define MOD 1048576
int n,t[3];
int main ()
{
    int i,aux,ind;
    freopen("12perm.in","r",stdin);
    freopen("12perm.out","w",stdout);
    scanf("%d",&n);
    if(n==1)
        printf("1\n");
    t[2]=2;t[0]=6;t[1]=12;
    int i3=2,i1=1;
    ind=6;
    for(i=5;i<=n;i++)
    {
        aux+=t[i1];
        t[i3]=(ind+t[i3]+t[i1])%MOD;
        ind+=2;
        i1 == 2 ? i1 = 0 : ++i1;
        i3 == 2 ? i3 = 0 : ++i3;
    }    
    printf("%d\n",t[n%3]);
    return 0;
}