#include <fstream>

using namespace std;

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

typedef long long ll;

const ll MD = 1 << 20;

ll N,Sol;

int main()
{
    fin >> N;

    ll A1 = 1,A2 = 2,A3 = 4,A4 = 8,
        B3 = 2,B4 = 4;

    if (N < 5)
    {
        switch (N)
        {
            case 1:fout << 1 << "\n";return 0;break;
            case 2:fout << 2 << "\n";return 0;break;
            case 3:fout << 6 << "\n";return 0;break;
            case 4:fout << 12 << "\n";return 0;break;
        }
    }

    for (ll i = 5;i <= N;i++)
    {
        ll aux = (A3 + A1 + 2) % MD;

        A1 = A2;
        A2 = A3;
        A3 = A4;
        A4 = aux;

        aux = (B3 + A2) % MD;

        B3 = B4;
        B4 = aux;
    }

    fout << A4 + B4 << "\n";

  return 0;
}