#include <fstream>
#define MOD 1048576
using namespace std;
ifstream in("12perm.in");
ofstream out("12perm.out");
int a[5];
int main()
{
    int n, i;
    in>>n;
    if(n==1) out<<1;
    else if(n==2) out<<2;
    else if(n==3) out<<6;
    else if(n==4) out<<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];
        }
        out<<a[4];
    }
}