#pragma region
#include <bits/stdc++.h>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef HOME
    ~debug() { cerr << endl; }
    eni(!= ) cerr << boolalpha << i; ris;
}
eni(== ) ris << range(begin(i), end(i));
}
sim, class b dor(pair < b, c > d) {
    ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
    *this << "[";
    for (auto it = d.b; it != d.e; ++it)
        *this << ", " + 2 * (it == d.b) << *it;
    ris << "]";
}
#else
    sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define ll long long
#define vll vector<ll>
const ll mod = 666'013;
#pragma endregion

// 0 1
// 2 3

vll multiply(vll a, vll b) {
    vll ans(4);
    ans[0] = (a[0] * b[0] % mod + a[1] * b[2] % mod) % mod;
    ans[1] = (a[0] * b[1] % mod + a[1] * b[3] % mod) % mod;
    ans[2] = (a[2] * b[0] % mod + a[3] * b[2] % mod) % mod;
    ans[3] = (a[2] * b[1] % mod + a[3] * b[3] % mod) % mod;
    return ans;
}

ll binpow(vll a, ll b) {
    vll ans = a;
    if (b == 0)
        return 0;
    while (b) {
        if (b & 1)
            ans = multiply(ans, a);
        a = multiply(a, a);
        b >>= 1;
    }
    return ans[0];
}

void solve() {
    vll fib = { 0, 1, 1, 1 };
    ll n;   fin >> n;
    fout << binpow(fib, n) << endl;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;  //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}