#include <bits/stdc++.h>
using namespace std;
ifstream fin("12perm.in");
ofstream fout("12perm.out");

const int MODULO=1048576;
int n;
/**const short Rmax=20;
int  st[Rmax],nr;
bool viz[Rmax];
inline int MODUL(intx,int y)
{
    int s=(x-y);
    if(s<0)
        return (-s);
    return s;
}
/*void BACK(int top)
{
    if(top==(n+1))
        ++nr;
    else if(top==1)
    {
        for(int i=1;i<=n;i++)
            if(!viz[i])
        {
            viz[i]=true;
            st[top]=i;
            BACK(top+1);
            viz[i]=false;
        }
    }
    else if(top>1)
    {
        for(int i=1;i<=n;i++)
            if(!viz[i] && MODUL(st[top-1],i)<3)
            {
                viz[i]=true;
                st[top]=i;
                BACK(top+1);
                viz[i]=false;
            }
    }
}
*/
int main()
{
    int x,y,z,r,sol;
    fin>>n;
    x=1;
    y=2;
    z=6;
    r=12;
    if(n==1)
        fout<<"1\n";
    else if(n==2)
        fout<<"2\n";
    else if(n==3)
        fout<<"6\n";
    else if(n==4)
        fout<<"12\n";
    else
    {
        for(int i=5;i<=n;i++)
        {
            sol=(r+y+(1LL*2*(i-2)%MODULO))%MODULO;
            x=y;
            y=z;
            z=r;
            r=sol;
        }
        fout<<sol<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}