#include <fstream>

#include <algorithm>

using namespace std;

const int MOD = 1048576;

int n;
int unu, doi, trei, sol;

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

    f >> n;

    unu = 2;
    doi = 6;
    trei = 12;
    for (int i = 5; i <= n; ++i) {
        sol = (trei + unu + 2 * (i - 2)) % MOD;
        unu = doi; 
        doi =  trei;
        trei = sol;
    }

    g << sol;
}