#include <iostream>
#include <fstream>

using namespace std;

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

const int MOD = 1048576;
//const int NMAX = 15000000 + 1;

int n, nr;
int rez[4];

/*
int x[NMAX];
bool pus[NMAX];


void scrie() {
    nr++; //cout << nr << ". ";
    //for (int i = 1; i <= n; i++) cout << x[i] << ' ';
    //cout << endl;
}

void back_tracking(int k) {
    if (k == n + 1) {
        scrie();
        return;
    }
    int a = x[k - 1];
    for (int i = -2; i <= 2; i++)
        if (a + i > 0 && a + i <= n && !pus[a + i]) {
            pus[a + i] = true;
            x[k] = a + i;
            back_tracking(k + 1);
            pus[a + i] = false;
        }
}
*/

void rezolva(int n) {
    rez[0] = 1;
    rez[1] = 2;
    rez[2] = 6;
    rez[3] = 12;
    if (n <= 4) {
        g << rez[n - 1] << '\n';
        return;
    }
    int rez_crt;
    for (int i = 5; i <= n; i++){
        rez_crt = (rez[3] + rez[1] + 2 * (i - 2)) % MOD;
        rez[0] = rez[1]; rez[1] = rez[2]; rez[2] = rez[3];
        rez[3] = rez_crt;
    }
    g << rez[3] << '\n';
}

int main() {
    f >> n;
    rezolva(n);
    return 0;
}