#include <bits/stdc++.h>
#define NMAX 15000008
#define MOD 1048576

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

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

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

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