#include<stdio.h>
//T[1] = 1, T[2] = 2, T[3] = 6, T[4] = 12;
//T[i] = T[i - 1] + T[i - 3] + 2 * (i - 2)

long N;

int main()
{
    freopen("12perm.in","r",stdin);
    freopen("12perm.out","w",stdout);
    scanf("%ld",&N);
    long aux;
    long r1=1,r2=2,r3=6,r4=12;
    if (N==1)
        printf("1\n");
    else if (N==2)
        printf("2\n");
    if (N==3)
        printf("6\n");
     else if(N==4)
            printf("12\n");
    else
    {
        for (long i=5;i<=N;i++)
        {
            aux=r4;
            r4=(r3+r1+2*(i-2))%1048576;
            r1=r2;
            r2=r3;
            r3=aux;
        }
        printf("%ld",r4);
    }
    return 0;
}