#include <bits/stdc++.h>

using namespace std;

const uint64_t MOD = 666013;

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

    static 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;
    }

    void operator,(int p) {
        if (p == 1) {
            return;
        }
        if (p % 2 == 0) {
            *this, p / 2;
            *this = mult(*this, *this);
        } else {
            Mat aux = *this;
            *this, p - 1;
            *this = mult(*this, aux);
        }
    }
};

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;

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