#include <fstream>
using namespace std;

ifstream fin("12perm.in");
ofstream fout("12perm.out");

const int MOD = 1048576;
int N;
int D[3], x;

int RidicareLaPutere( int a, int p );

int main()
{
    fin >> N;

    D[0] = 2, D[1] = 6, D[2] = 12;
    for ( int i = 5; i <= N; i++ )
    {
        x = ( D[2] + D[0] + ( (i - 2) * 2 ) ) % MOD;
        D[0] = D[1], D[1] = D[2], D[2] = x;
    }

    if ( N == 1 ) fout << "1";
    else
        if ( N == 2 ) fout << "2";
        else
            if ( N == 3 )
                fout << "6";
            else
                fout << x;

    fout << '\n';

    fin.close();
    fout.close();
    return 0;
}

int RidicareLaPutere( int a, int p )
{
    int rez = 1;

    while ( p > 0 )
    {
        if ( p % 2 )
        {
            rez = ( (1LL*rez) * (1LL*a) ) % MOD;
            p--;
        }

        a = ( (1LL*a) * (1LL*a) ) % MOD;
        p /= 2;
    }

    return rez;
}