#include<stdio.h>
#define MOD 1048576
int n,t[4];
int main ()
{
    int i,aux;
    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;
    for(i=5;i<=n;i++)
    {
        aux=2*(i-2);
        aux+=t[i%3];
        aux+=t[(i-1)%3];
        t[i%3]=aux%MOD;
    }
    printf("%d\n",t[n%3]);
    return 0;
}