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

const long long MOD = 20200111;

struct Mat {
    long long m[4][4];
};

Mat mul(const Mat &A, const Mat &B) {
    Mat C = {};
    for (int i = 0; i < 4; i++)
        for (int k = 0; k < 4; k++) {
            long long x = A.m[i][k];
            if (x == 0) continue;
            for (int j = 0; j < 4; j++) {
                C.m[i][j] = (C.m[i][j] + x * B.m[k][j]) % MOD;
            }
        }
    return C;
}

Mat mpow(Mat base, long long e) {
    Mat R = {};
    for (int i = 0; i < 4; i++) R.m[i][i] = 1;
    while (e > 0) {
        if (e & 1) R = mul(R, base);
        base = mul(base, base);
        e >>= 1;
    }
    return R;
}

long long solve(long long n) {
    if (n == 0) return 1;
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (n == 3) return 5;

    // Transition matrix for:
    // a[n] = 2a[n-1] + a[n-2] - a[n-4]
    Mat T = {{
        {2, 1, 0, MOD-1},  // MOD-1 is -1 mod M
        {1, 0, 0, 0},
        {0, 1, 0, 0},
        {0, 0, 1, 0}
    }};

    // We compute T^(n-3)
    Mat P = mpow(T, n - 3);

    // State vector for n = 3
    long long v[4] = {5, 2, 1, 1};

    long long result = 0;
    for (int j = 0; j < 4; j++)
        result = (result + P.m[0][j] * v[j]) % MOD;

    return result;
}

int main() {
    long long n;
    cin >> n;
    cout << solve(n) << "\n";
}