#include<cstdio>

int main()
{
    FILE *fin,*fout;
    fin=fopen("12perm.in","r");
    fout=fopen("12perm.out","w");

    int n,v1=2,v2=6,v3=12,v4=20,value=6;
    fscanf(fin,"%d",&n);

    if(n==1)
    {
        fprintf(fout,"1");
    }
    else if(n==2)
    {
        fprintf(fout,"2");
    }
    else if(n==3)
    {
        fprintf(fout,"6");
    }
    else if(n==4)
    {
        fprintf(fout,"12");
    }
    else
    {
        for(int i=5;i<=n;i++)
        {
            v4=v3+v1+value;
            if(v4>=1048576)
            {
                v4%=1048576;
            }
            value+=2;
            v1=v2;
            v2=v3;
            v3=v4;
        }
        fprintf(fout,"%d",v4);
    }
}