// dynamic by myself.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <vector>
#include <map>
#include <iostream>

using namespace std;



void numero_6() {
	int a, max;
	cin >> a >> max;
	vector<int>listS(a);
	for (size_t i = 0; i < a; i++)
	{
		cin >> listS[i];
	}
	vector<int> mapM(max + 1);
	mapM[0] = 0;
	mapM[1] = 1;
	
	for (int i = 2; i <= max; i++) {

		int minimum = 123412;
		for (int b = 0; b < a; b++) {
			if (listS[b] <= i) {
				if (mapM[i - listS[b]] < minimum) {
					minimum = mapM[i - listS[b]];
				}
			}
			else {
				break;
			}
		}
		mapM[i] = minimum + 1;
	}
	int legtobb = 0;
	for (auto key : mapM) {
		if (key > legtobb) {
			legtobb = key;
		}
	}
	cout << legtobb << '\n';
}

void numero_73() {
	int a, max, nem_tobb;
	cin >> a >> nem_tobb >>max;
	vector<int> listS(a);
	for (size_t i = 0; i < a; i++)
	{
		cin >> listS[i];
	}

	map<int, int> nemM;
	nemM[listS[0]] = 1;

	for (int i = listS[0] + 1; i <= max; i++)
	{
		//cerr << i << '\n';
		for (int b = 0; b < a; b++) {
			if (listS[b] > i) {
				break;
			}
			else {
				if (nemM[i - listS[b]] > 0) {
					int minimum = nemM[i - listS[b]];
					for (int k = 0; k < a; k++) {
						if ((nemM[i - listS[k]] > 0 && nemM[i - listS[k]] < minimum) || i - listS[k] == 0) {
							minimum = nemM[i - listS[k]];
							if (minimum == 0) {
								nemM[i] = 1;
								break;
							}
						}
					}
					nemM[i] = minimum + 1;
					break;
				}
				else if (i - listS[b] == 0) {
					nemM[i]++;
					break;
				}
			}
		}
	}

	// 6 3 50 2 3 11 13 17 25

	vector<int> nem_lehet;
	for (int i = 1; i <= max; i++) {
		if (!(nemM[i] > 0 && nemM[i] <= nem_tobb)) {
			nem_lehet.push_back(i);
		}

	}
	cout << nem_lehet.size() << '\n';
	for (size_t i = 0; i < nem_lehet.size(); i++)
	{
		cout << nem_lehet[i] << " ";
	}cout << '\n';
}
void trains() {
	cin.sync_with_stdio(false);
	cin.tie(nullptr);
	int stations, trains;
	cin >> stations >> trains;
	vector<vector<pair<int, int>>>listS(stations + 1);
	vector<pair<int,int>> lepesekS(stations + 1, {0, -1});
	for (int i = 0; i < trains; i++) {
		int k, n;
		cin >> k >> n;
		listS[n].push_back({i, k});
	}
	lepesekS[1].second = 0;
	for (int i = 2; i <= stations; i++) {


		for (int a = 0; a < listS[i].size(); a++) {
			if ((lepesekS[i].second == -1 || lepesekS[listS[i][a].second].second < lepesekS[i].second) && lepesekS[listS[i][a].second].second != -1) {
				lepesekS[i].second = lepesekS[listS[i][a].second].second + 1;
				lepesekS[i].first = listS[i][a].first;
			}
			
		}
	}
	if (lepesekS[stations].second == -1) {
		cout << 0 << '\n';
		return ;
	}

	vector<int>utS;
	while (stations > 1) {
		utS.push_back(lepesekS[stations].first);
		
	}
	cout << lepesekS[stations].second;
}


void epuletek() {
	long long a;
cin >> a;
	vector<vector<long long>>listS(a, vector<long long>(3));
	listS[0][0] = 1; //p
	listS[0][1] = 1; //z
	listS[0][2] = 1; //f
	int sum = 3;
	for (int i = 1; i < a; i++) {
	
		listS[i][0] = listS[i - 1][1] + listS[i - 1][2];
		listS[i][1] = listS[i - 1][2];
		listS[i][2] = listS[i - 1][0] + listS[i - 1][1] + listS[i - 1][2];


		sum = (listS[a - 1][0] + listS[a - 1][1] + listS[a - 1][2]) % 20160109;

		listS[i][0] %= 20160109;
		listS[i][1] %= 20160109;
		listS[i][2] %= 20160109;

	}
	
	cout << sum << '\n';
}

int main()
{
	epuletek();
}