#include <bits/stdc++.h>
#define NMAX 15000008
#define MOD 1048576
#pragma GCC optimize("O3")

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

int n, nr, val1, val2, val3, val4, val5, new_val = 34;

int main()
{
    fin >> n;
    val1 = 34;
    val2 = 20;
    val3 = 12;
    val4 = 6;
    val5 = 2;
    for (int i = 7; i <= n; i++)
    {
        new_val += val2 - val5 + 4;
        if (new_val >= MOD)
            new_val -= MOD;
        else if (new_val < 0)
            new_val += MOD;

        val5 = val4;
        val4 = val3;
        val3 = val2;
        val2 = val1;
        val1 = new_val;
    }
    fout << val1;
    return 0;
}