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

long long A[105];
long long B[105];
long long JardaB(int h);

long long JardaA(int n)
{
    if(n<=0)
        return 0;
    if(n==1)
        return 1;
    if(n==2)
        return 2;

    if(A[n]!=0)
        return A[n];

    A[n] = (JardaA(n-1)%20200111+JardaA(n-2)%20200111+2*JardaB(n-1)%20200111);
    return A[n];

}
long long JardaB(int n)
{
    if(n<=0)
        return 0;
    if(n==1)
        return 0;
    if(n==2)
        return 1;
    if(n==3)
        return 2;
    if(n==4)
        return 4;

    if(B[n]!=0)
        return B[n];

    B[n] = ((JardaA(n-2)%20200111+JardaB(n-2)%20200111+JardaB(n-1)%20200111))%20200111;
    return B[n];
}
int main()
{

    int N;
    cin >> N;
    /*for(int i = 0;i <= N; i++)
        cout << i << ":" << JardaA(i) << "-" << JardaB(i) << "\n";*/
    cout << JardaA(N) << "\n";
    return 0;
}