#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 15000000;
const int MOD = (1<<20) - 1;

int n;

int m[2][4];

//m[0] = N marg N - 1 int
//m[1] = N int N - 1 marg
//m[2] = N int N - 1 int
//2 = N marg N - 1 margine

int vis[30];int sol[30];

int mod(int x) {
	return x < 0 ? -x : x;
}

void back(int k, int& cnt) {

	if(k == n + 1) {
		for(int i = 1; i <= n; ++i)
			fout << sol[i] << ' ';
		fout << '\n'; 
		cnt++;
	}
	else

		for(int i = 1; i <= n; ++i)
			if(vis[i] == 0 && ( mod(sol[k - 1] - i) < 3 || k == 1 ) )  {
				vis[i] = 1;
				sol[k] = i;
				back(k + 1, cnt);
				vis[i] = 0;
			}
}

int main() {

	fin >> n;

	if(n == 1) fout << 1 << '\n'; 
	if(n == 2) fout << 2 << '\n';

	/*
	1 2 3
	1 3 2
	2 1 3
	2 3 1
	3 1 2
	3 2 1
	*/

	if(n > 3) {

		m[0][0] = 2;
		m[0][1] = 2;
		m[0][2] = 0;

		int state = 1;

		for(int i = 4; i <= n; ++i) {

			state = !state;

			m[!state][1] = (m[!state][0] + 2) & MOD; //=m[state][0], da dar alea lipite adica m[state][0] = m[!state][0] + 2
			m[!state][2] = (m[state][2] + m[state][1]) & MOD;
			m[!state][0] = (m[state][0] + m[state][1] + 2) & MOD;
		}

		fout << ( (m[!state][0] + m[!state][1] + m[!state][2] + 2) & MOD ) << '\n'; 

	}

	return 0;
}