#include <bits/stdc++.h>

#define MOD 666013

using namespace std;

class Matrix {
private:
    vector<vector<int>> M;
public:
    Matrix(int n, int m) {
        M.resize(n, vector<int>(m, 0));
    }

    int get(int i, int j) {
        return M[i][j];
    }

    void set(int i, int j, int val) {
        M[i][j] = val;
    }

    int lines() {
        return M.size();
    }

    int columns() {
        return M[0].size();
    }

    friend Matrix operator + (Matrix A, const Matrix& B) {
        assert(A.M.size() == B.M.size() && A.M[0].size() == B.M[0].size());
        for(size_t i = 0; i < A.M.size(); i++) {
            for(size_t j = 0; j < A.M[0].size(); j++) {
                A.M[i][j] = (A.M[i][j] + B.M[i][j]) % MOD;
            }
        }
        return A;
    }
    friend Matrix operator * (Matrix A, const Matrix& B) {
        assert(A.M[0].size() == B.M.size());
        Matrix C(A.M.size(), B.M[0].size());
        for(size_t i = 0; i < A.M.size(); i++) {
            for(size_t j = 0; j < B.M[0].size(); j++) {
                for(size_t k = 0; k < A.M[0].size(); k++) {
                    C.M[i][j] = (C.M[i][j] + 1LL * A.M[i][k] * B.M[k][j]) % MOD;
                }
            }
        }
        return C;
    }
};

Matrix logPow(Matrix base, int exp) {
    assert(base.lines() == base.columns());

    Matrix ans(base.lines(), base.columns());
    ans.set(0, 0, 1);
    ans.set(1, 1, 1);
    for(int i = 0; i <= 30; i++) {
        if(exp & (1 << i)) {
            ans = ans * base;
        }
        base = base * base;
    }

    return ans;
}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    int n;
    scanf("%d", &n);

    Matrix F0(2, 1);
    F0.set(1, 0, 1);

    Matrix L(2, 2);
    L.set(0, 1, 1);
    L.set(1, 0, 1);
    L.set(1, 1, 1);

    printf("%d", (logPow(L, n - 1) * F0).get(1, 0));
}