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

unordered_map<int, int> memo = {
    {0, 1}, {1, 2}, {2, 4}, {3, 10}, {4, 24}, {5, 56}
};
const int MOD = 20210108;

int t(int n) {
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    int cur;
    if (n % 2 == 0) {
        cur = (1LL * t(n / 2 - 1) * t(n / 2 + 1) + 2LL * (1LL * t(n / 2 - 3) * t(n / 2) + 1LL * t(n / 2 - 2) * t(n / 2 - 1))) % MOD;
    } else {
        cur = (1LL * t(n / 2) * t(n / 2 + 1) + 2LL * (1LL * t(n / 2 - 2) * t(n / 2) + 1LL * t(n / 2 - 1) * t(n / 2 - 1))) % MOD;
    }
    memo[n] = cur;
    return cur;
}

int main() {
    int n;
    cin >> n;
    cout << t(n) << "\n";
    return 0;
}