#include <iostream>
#include <fstream>
#include <cmath>
#define MOD 1048576

using namespace std;

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

int n, A, B, C;
long long 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;

    return 0;
}