#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");
unsigned long long dpA, dpB, dpC, dpAA, dpBB, dpCC, dpAAA;
int main()
{
    unsigned long long n, mod = (1<<20);
    cin >> n;
    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++)
    {
        dpA = (dpAA + dpCC)^mod;
        dpB = (dpAA + dpBB)^mod;
        dpC = (dpAAA + 2)^mod;
        dpAAA = dpAA;
        dpAA = dpA;
        dpBB = dpB;
        dpCC = dpC;
    }
    cout << (dpA + dpB + dpC) % mod;
}