#include <fstream>
#define MOD 1048576
using namespace std;

ifstream fin("12perm.in");
ofstream fout("12perm.out");

int a[5];

int main()
{
    int n, i;
    fin>>n;
    if(n==1) fout<<1;
    else if(n==2) fout<<2;
    else if(n==3) fout<<6;
    else if(n==4) fout<<12;
    else
    {
        a[0]=1;
        a[1]=2;
        a[2]=6;
        a[3]=12;
        for(i=5;i<=n;i++)
        {
            a[4]=(a[3]+a[1]+2*(i-2))%MOD;
            a[0]=a[1];
            a[1]=a[2];
            a[2]=a[3];
            a[3]=a[4];
        }
        fout<<a[4];
    }
}