#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 1048576 ;

int main()
{
    int n;
    fin >> n;

    int a = 2, b = 6, c = 12;
    if(n == 1)
        fout << 1;
    else if(n == 2)
        fout << 2;
    else if(n == 3)
        fout << 6;
    else if(n == 4)
        fout << 12;
    else {
        int i, ax;
        for(i = 5; i <= n; ++i){
            ax = a + c + 2 * (i - 2);
            while(ax > MOD)
                ax -= MOD;
            a = b;
            b = c;
            c = ax;
        }
        fout << c;
    }
    return 0;
}