#include<fstream>
#define MOD 1048576
using namespace std;
ifstream fi("12perm.in");
ofstream fo("12perm.out");
int n,a,b,c,i,aux;
int main()
{
    fi>>n;
    if(n==1)
        fo<<"1\n";
    if(n==2)
        fo<<"2\n";
    if(n==3)
        fo<<"6\n";
    if(n==4)
        fo<<"12\n";
    if(n>4)
    {
        a=12;
        b=6;
        c=2;
        for(i=5; i<=n; i++)
        {
            aux=(a+c+2*(i-2))%MOD;
            c=b;
            b=a;
            a=aux;
        }
        fo<<a<<"\n";
    }
    fi.close();
    fo.close();
    return 0;
}