#include <fstream>

using namespace std;

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

const int MOD = 1048576 - 1;

int N, a, b, c;

int main()
{
    in >> N;
    a = 2;  b = 6;  c = 12;
    for (int i = 5; i <= N; i++) {
        a = ((c + a + ((i - 2) << 1)) & MOD);
        swap (a, c);
        swap (a, b);
    }

    if (N == 1) out << "1\n";
    else if (N == 2) out << a << '\n';
    else if (N == 3) out << b << '\n';
    else out << c << '\n';

    return 0;
}