#include <bits/stdc++.h>
#define MOD 1048576
using namespace std;
long long v[7],n,nr;
int main()
{
    freopen("12perm.in","r",stdin);
    freopen("12perm.out","w",stdout);
    v[1]=1;
    v[2]=2;
    v[3]=6;
    v[4]=12;
    scanf("%d", &n);
    if(n<=4) printf("%d",v[n]);
    else
    {
        for(int i=5;i<=n;++i)
        {
            nr=v[4]+v[2]+2*(i-2);
            if(nr>=MOD) nr%=MOD;
            v[1]=v[2];
            v[2]=v[3];
            v[3]=v[4];
            v[4]=nr;
        }
        printf("%d\n",v[4]);
    }
    return 0;
}