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

namespace kfib {
    constexpr int MOD = 666013;
    typedef vector< vector<int> > matrix;

    matrix operator* (const matrix& lhs, const matrix& rhs) {
        matrix res(lhs.size(), vector<int>(rhs[0].size()));

        for (size_t i = 0; i < lhs.size(); ++i)
            for (size_t j = 0; j < rhs[0].size(); ++j)
                for (size_t k = 0; k < lhs[0].size(); ++k)
                    res[i][j] = int((res[i][j] + 1LL * lhs[i][k] * rhs[k][j]) % MOD);

        return res;
    }

    matrix raise_to_power(matrix base, int exponent) {
        matrix res({{1, 0}, {0, 1}});
        while (exponent > 0) {
            if (exponent & 1)
                res = res * base;
            exponent >>= 1;
            base = base * base;
        }

        return res;
    }
}

void solve() {
    int k;
    cin >> k;

    if (k == 0) {
        cout << 0 << endl;
        return;
    }
    if (k == 1) {
        cout << 1 << endl;
        return;
    }

    k -= 1;

    kfib::matrix base = {{1, 1}, {1, 0}};
    kfib::matrix final_matrix = kfib::raise_to_power(base, k);

    cout << final_matrix[0][0] << endl;
}

int main() {
    assert(freopen("kfib.in", "r", stdin));
    assert(freopen("kfib.out", "w", stdout));
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    solve();

    return 0;
}