#include <bits/stdc++.h>
#define mod 1048576

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

int main(){
    int n, i;
    fin >> n;
    int x[4] = {0, 1, 2, 6};
    if (n == 1)
        fout << 1;
    else if (n == 2)
        fout << 2;
    else if (n == 3)
        fout << 6;
    else{
        for (i=4; i<=n; i++){
            x[i%4] = x[((i%4+4)-1)%4] + 2 * x[((i%4+4)-3)%4] + 2 * (i-2);
            while (x[i%4] > mod)
                x[i%4] -= mod;
        }
        fout << x[n%4];
    }
    return 0;
}