#include <bits/stdc++.h>
using namespace std;

const int msk = (1 << 20) - 1;
int n, x[7], y[7];
void add(int &a, int b) {
	a += b;
	a &= msk;
}
int main() {
	ifstream cin("12perm.in");
	ofstream cout("12perm.out");

	cin >> n;
	x[0] = 1;
	x[1] = 1;
	x[2] = 2;
	y[3] = 2;
	x[3] = 4;
	y[4] = 4;
	x[4] = 8;
	int r = 4;
	for(int i = 5; i <= n; ++i) {
		r = (r + 1) % 6;
		x[r] = y[r] = 0;
		add(x[r], x[(r - 1 + 6) % 6]);
		add(x[r], 2);
		add(x[r], x[(r - 3 + 6) % 6]);
		add(y[r], y[(r - 1 + 6) % 6]);
		add(y[r], x[(r - 2 + 6) % 6]);
	}
	int ans = x[r];
	add(ans, y[r]);
	cout << ans;
}