#include <bits/stdc++.h>
#define M 1048576
using namespace std;
ifstream f("12perm.in");
ofstream g("12perm.out");
int main()
{int n,i,a,b,c,d;
f>>n;
if(n==1) g<<1;
if(n==2) g<<2;
if(n==3) g<<6;
if(n==4) g<<12;
if(n>=5)
{
    a=1;
    b=2;
    c=6;
    d=12;
    for(i=5;i<=n;i++)
    {
        a=(d+b+2*(i-2))%M;
        b=c;
        c=d;
        d=a;
    }
    g<<a;
}

    return 0;
}