#include <fstream>
#include <string>
#include <vector>
#include <cassert>

using namespace std;

const string IN_FILE = "kfib.in";
const string OUT_FILE = "kfib.out";
const int MOD = 666013;

typedef vector<vector<int>> Matrix;

inline int rows(const Matrix& a) {
    return int(a.size());
}

inline int columns(const Matrix& a) {
    return int(a[0].size());
}

inline Matrix unit(const int size) {
    auto a = Matrix(size, vector<int>(size));
    for (int i = 0; i < size; i++) {
        a[i][i] = 1;
    }
    return a;
}

Matrix multiply(const Matrix& a, const Matrix& b) {
    const int m = rows(a);
    const int n = columns(a);
    const int p = columns(b);
    assert(n == rows(b));
    Matrix c = Matrix(m, vector<int>(p));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < p; j++) {
            for (int k = 0; k < n; k++) {
                c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % MOD;
            }
        }
    }
    return c;
}

Matrix pow(const Matrix& a, const int p) {
    const int n = rows(a);
    assert(n == columns(a));
    if (p == 0) return unit(n);
    return p % 2 == 1
            ? multiply(a, pow(a, p -1))
            : pow(multiply(a, a), p / 2);
}

int readInput() {
    ifstream in(IN_FILE);
    int n;
    in >> n;
    in.close();
    return n;
}

void writeOutput(const int result) {
    ofstream out(OUT_FILE);
    out << result << "\n";
    out.close();
}

int main() {
    const int n = readInput();
    const auto z = Matrix({{0, 1}, {1, 1}});
    const auto result = multiply(pow(z, n), Matrix({{0}, {1}}));
    writeOutput(result[0][0]);
    return 0;
}