// ConsoleApplication1.cpp : This file contains the 'main' function. Program execution begins and ends there.
//


/*


          EZ ITT KEVINKE12 KÓDJA, CSAK TESZTELEM, HOGY MIVEL TUDOTT MAGÁNAK OLYAN ALACSONY MEMÓRIAHASZNÁLATOT VARÁZSOLNI


*/

#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;
}