#include <fstream>

const int MOD = 1048576;

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

long long N,A,B,C,sol;

int main()
{
    f >> N;
    A = 2;
    B = 6;
    C = 12;

    if (N == 1) g << "1";
    if (N == 2) g << A;
    if (N == 3) g << B;

    if (N <=3 ) return 0;

    for (int i = 5; i <= N; ++i)
    {
        sol = (A + C + 2*(i-2)) % MOD;
        A = B;
        B = C;
        C = sol;
    }

    g << C;

    f.close();
    g.close();
    return 0;
}