#include <fstream>

using namespace std;

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

typedef long long ll;

const ll MD = 1 << 20;

ll N,Sol;
ll A[5];

int main()
{
    fin >> N;

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

    if (N < 5)
    {
        fout << A[N] << "\n";
        return 0;
    }

    for (ll i = 5;i <= N;i++)
    {
        A[1] = A[2];
        A[2] = A[3];
        A[3] = A[4];
        A[4] = (A[3] + A[1] + 1LL * 2 * (i - 2)) % MD;
    }

    fout << A[4] << "\n";

  return 0;
}