#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

#include <cstdio>
#include <cstring>
#define mod 666013

using namespace std;

int N;
int MAT[3][3], SOL[3][3];

inline void mult(int A[][3], int B[][3], int C[][3]) {
    int i, j, k;
    for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++)
            for (k = 0; k < 2; k++)
                C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % mod;

}

inline void lg_power(int P, int M[][3]) {
    int C[3][3], AUX[3][3], i;

    memcpy(C, MAT, sizeof(MAT));
    M[0][0] = M[1][1] = 1;

    for (i = 0; (1 << i) <= P; i++) {
        if (P & (1 << i)) {
            memset(AUX, 0, sizeof(AUX));
            mult(M, C, AUX);
            memcpy(M, AUX, sizeof(AUX));
        }

        memset(AUX, 0, sizeof(AUX));
        mult(C, C, AUX);
        memcpy(C, AUX, sizeof(C));
    }
}

void solve() {
    fin >> N;

    MAT[0][0] = 0; MAT[0][1] = 1; MAT[1][0] = 1; MAT[1][1] = 1;

    lg_power(N - 1, SOL);

    fout << SOL[1][1] << '\n';
}

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

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

    return 0;
}