#include <bits/stdc++.h>

using namespace std;

const uint64_t MOD = 666013;

struct Mat {
    uint64_t v[2][2];
};

Mat mult(Mat m1, Mat m2) {
    Mat res;
    res.v[0][0] = (1LL * m1.v[0][0] * m2.v[0][0] + 1LL * m1.v[0][1] * m2.v[1][0]) % MOD;
    res.v[0][1] = (1LL * m1.v[0][0] * m2.v[0][1] + 1LL * m1.v[0][1] * m2.v[1][1]) % MOD;
    res.v[1][0] = (1LL * m1.v[1][0] * m2.v[0][0] + 1LL * m1.v[1][1] * m2.v[1][0]) % MOD;
    res.v[1][1] = (1LL * m1.v[1][0] * m2.v[0][1] + 1LL * m1.v[1][1] * m2.v[1][1]) % MOD;

    return res;
}

Mat exp(Mat m, int p) {
    if (p == 1) {
        return m;
    }
    if (p % 2 == 0) {
        Mat m1 = exp(m, p / 2);
        return mult(m1, m1);
    } else {
        return mult(m, exp(m, p - 1));
    }
};

ifstream fin("kfib.in");
ofstream fout("kfib.out");

int main() {
    int n;
    fin >> n;

    Mat z;
    z.v[0][0] = 0;
    z.v[0][1] = 1;
    z.v[1][0] = 1;
    z.v[1][1] = 1;

    Mat res = exp(z, n);

    fout << res.v[0][1] << "\n";
}