// ConsoleApplication1.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <iostream>
typedef long long int64;
size_t jardahossz = 100;
using namespace std;
int main()
{
/*
szamoljuk meg a nyitott lerakasokat, hany fele keppen lehet n hosszu jardat lerakni, hogy mindenhol "kotesben legyen" es a vegen kilogjon egy elem (alul vagy felül nem számít)
2 hosszu nyitott - csak egy Laci betu
3 hosszu nyitott - Laci + lapos
n hosszu nyitott = n - 1 hosszu nyitott (lapossal bovitve) + n-2 hosszu nyitott (T alakkal bovitve)
n + 1 hosszu zart = n hosszu nyitott (Lacival lezarva) * 2 ( vizszintes tengelyre tukrozve, már számít az alul vagy felül )
-> a bonthatatlan zárt lerakások fibonacci szerû sorozatot alkotnak
*/
//zart[n] = n hosszu bonthatatlan lerakas hany fele van
//int64 zart[jardahossz + 1];
//zart[1] = 1;
//zart[2] = 1;
//zart[3] = 2;
//zart[4] = 2;
//size_t idx = 5;
//do{
// zart[idx] = (zart[idx - 1] + zart[idx - 2]) % 20200111;
//printf_s("zart %u: %u\n", idx, zart[idx]);
//} while (++idx <= jardahossz);
/*
osszes[1] = osszes[0] * zart[1] = 1
osszes[2] = osszes[1] * zart[1] + osszes[0] * zart[2] = 2
osszes[3] = osszes[2] * zart[1] + osszes[1] * zart[2] + osszes[0] * zart[3] = 5
osszes[4] = osszes[3] * zart[1] + osszes[2] * zart[2] + osszes[1] * zart[3] + osszes[0] * zart[4] = 11 5 2 2 2
osszes[5] = osszes[4] * zart[1] + osszes[3] * zart[2] + osszes[2] * zart[3] + osszes[1] * zart[4] + osszes[0] * zart[5]
osszes[6] = osszes[5] * zart[1] + osszes[4] * zart[2] + osszes[3] * zart[3] + osszes[2] * zart[4] + osszes[1] * zart[5] + osszes[0] * zart[6]
osszes[7] = osszes[6] * zart[1] + osszes[5] * zart[2] + osszes[4] * zart[3] + osszes[3] * zart[4] + osszes[2] * zart[5] + osszes[1] * zart[6] + osszes[0] * zart[7]
Az osszes larakasok sorozata is majdnem fibonacci sorozatot alkot, mert zart[n] = zart[n-1] + zart[n-2] ha n>=5.
zart[2] = zart[1] + 0
zart[1] + zart[2] = zart[3]
viszont zart[2] + zart[3] - 1 = zart[4]
tehát osszes[n] = osszes[n - 1] * zart[1] + osszes[n - 1] + osszes[n - 2] - osszes[n - 4] * 1
osszes[n] = 2 * osszes[n - 1] + osszes[n - 2] - osszes[n - 4]
*/
int64 osszes[jardahossz + 1];
osszes[0] = 1;
osszes[1] = 1;
osszes[2] = 2;
osszes[3] = 5;
osszes[4] = 11;
size_t idx = 5;
cin >> jardahossz;
do {
osszes[idx] = (((osszes[idx - 1] * 2) % 20200111 + osszes[idx - 2]) % 20200111 - osszes[idx - 4]) % 20200111;
osszes[idx] = osszes[idx] < 0 ? 20200111 + osszes[idx] : osszes[idx];
//std::cout << idx << " " << osszes[idx] << std::endl;
} while (++idx <= jardahossz);
cout << osszes[jardahossz] << "\n";
return 0;
}