#include <bits/stdc++.h>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define int long long
const int MOD = 666013;
int n;

struct Iris {
    int a, b, c, d;

    void applyMod() { a %= MOD, b %= MOD, c %= MOD, d %= MOD; }
};

inline Iris produs(Iris a, Iris b) {
    Iris rez;
    rez.a = a.a * b.a + a.b * b.c;
    rez.b = a.a * b.b + a.b * b.d;
    rez.c = b.a * a.c + b.c * a.d;
    rez.d = a.c * b.b + a.d * b.d;
    rez.applyMod();
    return rez;
}

inline int kFib(Iris A, int n) {
    Iris p = {1, 0, 0, 1};
    while(n) {
        if(n & 1) p = produs(p, A);
        A = produs(A, A), n /= 2;
    }
    return p.a;
}

signed main()
{
    fin >> n;
    if(n == 0) fout << 0;
    else fout << kFib({1, 1, 1, 0}, n - 1);

    return 0;
}