#include <bits/stdc++.h>
using namespace std;

const int MODULO=1048576;
int main()
{
    int x,y,z,r,sol,n;
    ifstream fin("12perm.in");
    ofstream fout("12perm.out");
    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;
            x=y;
            y=z;
            z=r;
            r=sol;
        }
        fout<<sol<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}