#include <iostream>
#include <vector>
using namespace std;

struct adat
{
    int egesz,lyukas;
};

vector <adat> x;
int n,i;
int main()
{
    cin>>n;

    x.resize(n+1);

    x[1].egesz=1;
    x[2].egesz=2;
    x[3].egesz=5;
    x[2].lyukas=2;
    x[3].lyukas=4;
    for(i=4; i<=n; ++i)
    {
        x[i].egesz=((x[i-1].egesz+(2*x[i].egesz)%20200111)%20200111+x[i-2].lyukas)%20200111;
        x[i].lyukas=((x[i-1].lyukas+(2*x[i-2].egesz)%20200111)%20200111+x[i-2].lyukas)%20200111;
    }

    cout<<x[n].egesz1;
    return 0;
}