#include <bits/stdc++.h>

#define MOD 1048576

int N;

std::ifstream In ("12perm.in");
std::ofstream Out("12perm.out");

void Citire() {
    In >> N;
}

void Rezolvare() {
    if (N == 1) {
        Out << 1 << '\n';
        return;
    }
    if (N == 2) {
        Out << 2 << '\n';
        return;
    }
    if (N == 3) {
        Out << 6 << '\n';
        return;
    }
    if (N == 4) {
        Out << 12 << '\n';
        return;
    }

    long long A, B, C, D;
    A = 2;
    B = 6;
    C = 12;
    for (long long i=5; i<=N; ++i) {
        D = C + A  + 2 * (i-2);
        D %= MOD;
        A = B;
        B = C;
        C = D;
    }   Out << D << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}