#include <fstream>

using namespace std;

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

const int MOD = 1048576;
int N, v[] = {0, 1, 2, 6, 12};
int nra, nrb, nrc;

int main()
{
    fin >> N;

    if(N <= 4)
        {
            fout << v[N];
            return 0;
        }

    nra = 8, nrb = 8, nrc = 3;

    for(int i = 5; i <= N; i++)
    {
        int save_nrb = nrb;
        nra = nra + nrb;
        nrb = nrb + nrc;
        nrc = save_nrb;

        nra %= MOD;
        nrb %= MOD;
        nrc %= MOD;
    }

    fout << (nra + nrb + nrc) % MOD;

    return 0;
}