#include <bits/stdc++.h>

using namespace std;

const uint64_t MOD = 666013;

struct Matrix {
    vector<vector<uint64_t>> v, w;
    Matrix() {}
    Matrix(int n, int m) { v.clear(); w.clear(); v.assign(n, vector<uint64_t>(m)); }
    inline int height() const { return (int) v.size(); }
    inline int width() const { return (int) v[0].size(); }
    inline uint64_t& at(int i, int j) { return v[i][j]; }
    inline const uint64_t& at(int i, int j) const { return v[i][j]; }
    static Matrix identity(int n) {
        Matrix A(n, n);
        for (int i = 0; i < n; i++) A.at(i, i) = 1ULL;
        return A;
    }
    inline static Matrix identity(const Matrix& A) { return identity(A.height()); }
    Matrix& operator*=(const Matrix& B) {
        int n = height(), m = width(), p = B.height(), q = B.width();
        assert(m == p);
        w.assign(n, vector<uint64_t>(m, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < q; j++) {
                uint64_t x = 0ULL;
                for (int k = 0; k < m; k++) x += ((at(i, k) % MOD) * B.at(k, j) % (MOD)) % MOD, x %= MOD;
                w[i][j] = x % MOD;
            }
        }
        v.swap(w);
        return *this;
    }
};
Matrix operator^(const Matrix& t, unsigned long long k) {
    Matrix A = t, B = Matrix::identity(t);
    while (k > 0) {
        if (k & 1) B *= A;
        A *= A;
        k /= 2;
    }
    return B;
}

int main() {
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    Matrix Z(2, 2);
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            Z.at(i, j) = 1ULL;
        }
    }
    Z.at(0, 0) = 0ULL;
    Matrix init(1, 2);
    init.at(0, 0) = 0ULL;
    init.at(0, 1) = 1ULL;
    int k; cin >> k;
    init *= Z^(k - 1);
    cout << init.at(0, 1) << endl;
}