#include <bits/stdc++.h>
using namespace std;

//vector <int> v;
int n, sol[] = {1, 2, 6, 12};

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

    f>>n;
    /*
    for(int i=1; i<=n; i++)
        v.push_back(i);

    do {
        bool ok = true;
        for(int i=0; i<v.size()-1 && ok; i++)
            if(abs(v[i] - v[i+1]) > 2)
                ok = false;

        sol += ok;
    } while(next_permutation(v.begin(), v.end()));
    */

    for(int i=5; i<=n; i++) {
        int current = (sol[3] + sol[1] + 2 * (i-2)) % 1048576;
        for(int j=0; j<3; j++)
            sol[j] = sol[j+1];
        sol[3] = current;
    }

    g<<sol[3]<<"\n";
    return 0;
}