#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];
int main()
{
    int n, mod = (1<<20);
    cin >> n;
    dpA[4] = 4;dpB[4] = 4;
    dpC[4] = 4;dpA[3] = 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[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;
}