#include <iostream>
#include <fstream>
using namespace std;
ifstream in("12perm.in");
ofstream out("12perm.out");
const int maxn = 15000005;
const int mod = (1 << 20);
int A[maxn];
int B[maxn];
int main()
{
    int n;
    in >> n;
    A[1] = 1;
    B[1] = 0;
    A[2] = 2;
    B[2] = 0;
    A[3] = 4;
    B[3] = 2;
    A[4] = 8;
    B[4] = 4;
    if(n < 5)
    {
        out << A[n] + B[n] << "\n";
        return 0;
    }
    int aiminus3 = A[2];
    int aiminus2 = A[3];
    int aiminus1 = A[4];
    int biminus1 = B[3];
    int aact = 0;
    int bact = 0;
    for(int i = 5; i <= n; i++)
    {
        aact = aiminus1 + aiminus3 + 2;
        bact = biminus1 + aiminus2;
        aact = aact % mod;
        bact = bact % mod;
        aiminus3 = aiminus2;
        aiminus2 = aiminus1;
        aiminus1 = aact;
        biminus1 = bact;
    }
    out << (aact + bact) % mod << "\n";
    return 0;
}