#include<fstream>
#include<cstring>
#include<cmath>
#include<algorithm>

#define MOD 1048576

using namespace std;

ifstream fin("12perm.in");
ofstream fout("12perm.out");
int T[15000001], n;
int main()
{
    T[1] = 1;
    T[2] = 2;
    T[3] = 6;
    T[4] = 12;
    fin >> n;
    for(int i=5; i<=n; i++) T[i] = T[i-1] + T[i-3] + 2*(i-2), T[i] %= MOD;
    fout << T[n];
    return 0;

}