#include <fstream>

using namespace std;

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

int N;
int P[2][4];

/*
 * 0 - unite si N la margine
 * 1 - unite si N-1 la margine
 * 2 - unite si in interior
 * 3 - despartite si N-1 in interior
 * 4 - despartite si N-1 la margine
 */

int power(int x, int y)
{
	if (y == 0) return 1;
	if (y & 1) return (1LL * x * power(x, y - 1)) & ((1LL << 20) - 1);
	return power((1LL * x * x) & ((1LL << 20) - 1), y >> 1);
}

int main()
{
	ifstream fin("12perm.in");
	ofstream fout("12perm.out");
	
	fin >> N;
	if (N == 1) fout << 1 << '\n';
	if (N == 2) fout << 2 << '\n';
	if (N >= 3)
	{
		int act = 0;
		
		P[act][0] = 2;
		P[act][1] = 2;
		P[act][2] = 0;
		P[act][3] = 0;
		P[act][4] = 2;
		for (int i = 4; i <= N; ++i)
		{
			act = !act;
			
			P[act][0] = (P[!act][0] + P[!act][3] + P[!act][4]) & MOD;
			P[act][1] = P[!act][0];
			P[act][2] = (P[!act][1] + P[!act][2]) & MOD;
			P[act][3] = P[!act][1];
			P[act][4] = P[!act][4];
		}
		
		fout << ((P[act][0] + P[act][1] + P[act][2] + P[act][3] + P[act][4]) & MOD);
	}
	
	fin.close();
	fout.close();
}