#include <fstream>
#include <vector>
#define int int64_t
#define MOD 666013
using namespace std;

ifstream cin("kfib.in");
ofstream cout("kfib.out");


vector<vector<int>> mul_mat(const vector<vector<int>> &A, const vector<vector<int>> &B) {
    vector<vector<int>> C(2, vector<int>(2));
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            C[i][j] = 0;
            for (int k = 0; k < 2; k++) {
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
            }
        }
    }
    return C;
}


vector<vector<int>> exp_mat(vector<vector<int>> base, int e) {
    vector<vector<int>> res = {{1, 0}, {0, 1}}; 
    while (e > 0) {
        if (e & 1)
            res = mul_mat(res, base);
        base = mul_mat(base, base);
        e >>= 1;
    }
    return res;
}

int32_t main() {
    int n;
    cin >> n;

    if (n == 0) {
        cout << 0;
        return 0;
    }

    vector<vector<int>> fibMat = {{0, 1}, {1, 1}};
    auto ans = exp_mat(fibMat, n - 1);

    cout << ans[1][1] % MOD; // F(n)
}