#include <bits/stdc++.h>
#define int ll
using namespace std;
using ll = long long;
using vi = vector<int>;
using vii = vector<vi>;
const vii init = {
    {1, 0},
    {0, 1}
};
const vii nextfib = {
    {0, 1},
    {1, 1}
};
const vii fibinit = {
    {0, 1}
};

const int MOD = 666'013;

vii operator*(vii a, vii b) {
    int n = a.size();
    int m = b[0].size();
    int k = a[0].size();
    assert(a[0].size() == b.size());
    vii ans(n, vi(m));
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < m; j ++) {
            for(int g = 0; g < k; g ++) {
                ans[i][j] = (ans[i][j] + a[i][g] * b[g][j] % MOD) % MOD;
            }
        }
    }
    return ans;
}

vii pwr(vii a, int p) {
    if(!p)
        return init;
    if(p & 1)
        return a * pwr(a, p - 1);
    return pwr(a * a, p >> 1);
}

signed main() {
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    cin.tie(0)->sync_with_stdio(0);
    
    int k; cin >> k;
    cout << (fibinit * pwr(nextfib, k))[0][0];
}