#include <stdio.h>

int main()
{
    long int i,n,t1,t4,t3,aux;
    FILE *r;
    r=fopen("12perm.in","r");
    fscanf(r,"%ld",&n);
    fclose(r);
    r=fopen("12perm.out","w");
    t1=2;
    t3=12;
    if (n==1)
        fprintf(r,"1");
    if (n==2)
        fprintf(r,"2");
    if (n==3)
        fprintf(r,"6");
    if (n==4)
        fprintf(r,"12");
    for (i=5;i<=n;i++)
    {

        t4=(t3+t1+2*(i-2));

        if (t4>1048576)
            t4=t4%1048576;

        if (i==5)
            t1=6;
        else
            t1=aux;
        aux=t3;
        t3=t4;
    }
    fprintf(r,"%ld",t4);
    fclose(r);
return 0;
}