#include <fstream>
#define md 1048576

using namespace std;

ifstream f("12perm.in");
ofstream g("12perm.out");

long long n,t1,t2,t3,t4,i,aux;

int main()
{
    f>>n;
    t1=1;
    t2=2;
    t3=6;
    t4=12;
    for(i=5;i<=n;i++)
    {
        aux=t4+t2+2*(i-2);
        if(aux>md) aux-=md;
        t1=t2;
        t2=t3;
        t3=t4;
        t4=aux;
    }
    g<<t4;


    return 0;
}