#include <fstream>
#include <math.h>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
//#include <unordered_map>
#include <iomanip>
#include <time.h>
#include <stdio.h>
#include <bitset>
#include <map>
#include <ctime>
#include <stdlib.h>
#define MAX 500000000000
//#include <iostream>
//#include <windows.h>
#include <deque>
//#include "PEZai.h"
//#include <Tlhelp32.h>
using namespace std;
ifstream cin("12perm.in");
ofstream cout("12perm.out");
//ifstream cin("quadratum.in");
//ofstream cout("quadratum.out");
//long long dpA[15000004], dpB[15000004], dpC[15000004];
long long dpA, dpB, dpC, dpAA, dpBB, dpCC, dpAAA;
int main()
{
    int n, mod = (1<<20);
    cin >> n;
   // dpA[4] = 4;dpB[4] = 4;
  //  dpC[4] = 4;dpA[3] = 2;
    dpAA = dpA = 4;
    dpBB = dpB = 4;
    dpCC = dpC = 4;
    dpAAA = 2;
    if(n == 1){
        cout << 1;
        return 0;
    }
    if(n == 2){
        cout << 2;
        return 0;
    }
    if(n == 3){
        cout << 6;
        return 0;
    }
    for(int i = 5; i <= n; i++)
    {
        if(dpAA + dpCC >= mod)
            dpA = (dpAA + dpCC) % mod;
        else
            dpA = dpAA + dpCC;
        if(dpAA + dpBB >= mod)
            dpB = (dpAA + dpBB) % mod;
        else
            dpB = dpAA + dpBB;
        if(dpAAA + 2 >= mod)
            dpC = (dpAAA + 2) % mod;
        else
            dpC = dpAAA + 2;
        dpAAA = dpAA;
        dpAA = dpA;
        dpBB = dpB;
        dpCC = dpC;
    }
    cout << (dpA + dpB + dpC) % mod;
   /* for(int i = 5; i <= n; i++)
    {
        dpA[i] = (dpA[i - 1] + dpC[i - 1]) % mod;
        dpB[i] = (dpB[i - 1] + dpA[i - 1]) % mod;
        dpC[i] = (dpA[i - 2] + 2) % mod;
    }
    cout << (dpA[n] + dpB[n] + dpC[n]) % mod;*/
}