#include <fstream>

using namespace std;

const int NMAX = 15e6 + 1;
const int MOD = 1048576;

int N, d[NMAX];

int main()
{
    ifstream fin("12perm.in");

    fin >> N;

    fin.close();

    d[1] = 1;
    d[2] = 2;
    d[3] = 6;
    d[4] = 12;

    for(int i = 5; i <= N; ++i)
        d[i] = (d[i - 3] + d[i - 1] + 2 * (i - 2)) & (MOD - 1);

    ofstream fout("12perm.out");

    fout << d[N];

    fout.close();

    return 0;
}