#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 666013;

int K;

template<class T>
pair<uint64_t, uint64_t> nth_fibonacci(T n, T mod) {
    if (n == 0) {
        return make_pair(0, 1);
    }
    pair<uint64_t, uint64_t> Fk = nth_fibonacci(n >> 1, mod);
    pair<uint64_t, uint64_t> F2k;
    F2k.first = (Fk.first * ((mod + 2 * Fk.second % mod - Fk.first) % mod)) % mod;
    F2k.second = (Fk.first * Fk.first % mod + Fk.second * Fk.second % mod) % mod;
    if ((n & 1) == 0) {
        return F2k;
    }
    else {
        return make_pair(F2k.second, (F2k.first + F2k.second) % mod);
    }
}

int main()
{
    fin >> K;
    fout << nth_fibonacci(K, MOD).first;
    return 0;
}