#include <iostream>

using namespace std;

long long s(long long n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (n == 3) return 5;
    if (n == 4) return 11;

    long long a = 1, b = 2, c = 5, d = 11;
    const long long MOD = 20200111;

    for (long long i = 0; i < n - 4; i++) {
        long long next = (2 * d + c - a) % MOD;
        if (next < 0) next += MOD;
        a = b;
        b = c;
        c = d;
        d = next;
    }
    return d;
}

int main() {
    long long n;
    cin >> n;
    cout << s(n) << endl;
    return 0;
}