#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define MOD 666013
ifstream fin("kfib.in");
ofstream fout("kfib.out");
struct matrix {
    ull a, b, c, d;
    matrix() {}
    matrix(int aa, int bb, int cc, int dd) : a(aa), b(bb), c(cc), d(dd) {}
    matrix operator*(matrix m) {
        matrix r;
        r.a = (a*m.a + b*m.c) % MOD;
        r.b = (a*m.b + b*m.d) % MOD;
        r.c = (c*m.a + d*m.c) % MOD;
        r.d = (c*m.b + d*m.d) % MOD; 
        return r;
    }
}Z(0, 1, 1, 1);
matrix power(matrix n, ull p) {
    matrix x(1, 0, 0, 1);
    for (ull i = 0; (1 << i) <= p; i++) {
        if (p&(1<<i)) {
            x = x*n;
        }
        n = n*n;
    }
    return x;
}
int main() {
    ull p;
    fin >> p;
    if (!p) {
        fout << 0;
        return 0;
    }
    Z = power(Z, p - 1);
    fout << Z.d;
    fin.close();
    fout.close();
    return 0;
}