#include <fstream>
#include <vector>
#include <climits>
#define ll long long
using namespace std;

const int NMAX = 15000000;

const int MOD = 1048576;
int d[NMAX + 1];

int main()
{
    ifstream cin("12perm.in");
    ofstream cout("12perm.out");
    //cout << (sizeof(d))/1024.0;
    int n, i, j;
    cin >> n;
    d[1] = 1;
    d[2] = 2;
    d[3] = 6;
    d[4] = 12;
    for (i = 5; i <= n; i++)
    {
        d[i] = (d[i - 1] + d[i - 3] + 2 * (i - 2)) % MOD;
    }
    cout << d[n];
}