#include <fstream>

using namespace std;

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

const int MOD = 1048576;
int N, nra, nrb, nrc;

int main()
{
    fin >> N;

    if(N == 1)
    {
        fout << 1;
        return 0;
    }
    else if(N == 2)
    {
        fout << 2;
        return 0;
    }
    else if(N == 3)
    {
        fout << 6;
        return 0;
    }

    nra = 4;
    nrb = 2;
    nrc = 2;

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

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

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

    return 0;
}