#define F "kfib"
//#define DEBUG

/*    _            _ _
     | |          (_) |
   __| | _____   ___| | _____  _____
  / _` |/ _ \ \ / / | |/ _ \ \/ / _ \
 | (_| |  __/\ V /| | |  __/>  <  __/
  \__,_|\___| \_/ |_|_|\___/_/\_\___| */
#include <bits/stdc++.h>
using namespace std;

#ifdef F
ifstream fi("" F ".in");
ofstream fo("" F ".out");
#else
#define fi cin
#define fo cout
#endif

#define endl '\n'

#ifdef DEBUG
#define dbg(x)  cerr << x
#else
#define dbg(x)  ;
#endif // DEBUG

inline void __hook_main() __attribute__((always_inline));
int main()
{
#ifndef F
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
#endif
    __hook_main();
    return 0;
}

#define main inline void __hook_main()
/* --------------------------------------- */

#define ll long long

const int MOD = 666013;
#define m(x)    ((x)%MOD)
struct matrix {
    ll a[4];
}
matrix_identity({1,0,0,1});

matrix mult(matrix a, matrix b) {
    matrix res;
    res.a[0] = m(m(a.a[0] * b.a[0]) + m(a.a[2] * b.a[1]));
    res.a[1] = m(m(a.a[1] * b.a[0]) + m(a.a[3] * b.a[1]));
    res.a[2] = m(m(a.a[0] * b.a[2]) + m(a.a[2] * b.a[3]));
    res.a[3] = m(m(a.a[1] * b.a[2]) + m(a.a[3] * b.a[3]));
    return res;
}

matrix log_pow(matrix a, ll pow) {
    if(pow == 0) return matrix_identity;
    matrix a2 = log_pow(a, pow >> 1);
    if(!(pow & 1))
        return mult(a2, a2);
    return mult(mult(a2, a2), a);
}

void print_mat(matrix* m) {
    dbg(m->a[0] << ' ' << m->a[1] << endl << m->a[2] << ' ' << m->a[3] << endl);
}

main {
    ll N;
    fi >> N;
    matrix A({0,1,1,1});
    matrix res = log_pow(A, N);
    print_mat(&res);
    fo << res.a[1];
}