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

#define ll long long
#pragma endregion
const ll mod = 666013;
#define vll vector<ll>

// 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;
    ans[1] = a[0] * b[1] % mod + a[1] * b[3] % mod;
    ans[2] = a[2] * b[0] % mod + a[3] * b[1] % mod;
    ans[3] = a[2] * b[1] % mod + a[3] * b[3] % mod;
    return ans;
}

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

void solve() {
    vll fib = { 0, 1, 1, 1 };
    ll n;   fin >> n;
    fib = binpow(fib, n - 1);
    fout << fib[1] << 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;
}