#include <fstream>

using namespace std;
const int Mod = 666013;
using ll = long long;
class twobytwo {
private:
    ll a[2][2];
public:
    twobytwo(ll _a[2][2]) {a[0][0] = _a[0][0], a[0][1] = _a[0][1], a[1][0] = _a[1][0], a[1][1] = _a[1][1];}
    twobytwo operator *(const twobytwo& other) {
        ll res[2][2];
        res[0][0] = (a[0][0] * other.a[0][0] + a[0][1] * other.a[1][0]) % Mod;
        res[0][1] = (a[0][0] * other.a[0][1] + a[0][1] * other.a[1][1]) % Mod;
        res[1][0] = (a[1][0] * other.a[0][0] + a[1][1] * other.a[1][0]) % Mod;
        res[1][1] = (a[1][0] * other.a[0][1] + a[1][1] * other.a[1][1]) % Mod;
        return twobytwo(res);
    }
    int prod1() {return (a[1][0] + a[1][1]) % Mod;}
};
ll Zinit[2][2] = {{0, 1}, {1, 1}};
const twobytwo Z(Zinit);
twobytwo quick_pow(twobytwo a, int k) {
    twobytwo res = a; k--;
    while(k > 0) {
        if(k & 1) res = res * a;
        a = a * a;
        k >>= 1;
    }
    return res;
}
ifstream fin("kfib.in");
ofstream fout("kfib.out");

int main()
{
    int n;
    fin >> n;
    if(n == 0) fout << 0;
    if(n == 1 || n == 2) fout << 1;
    if(n > 2) fout << quick_pow(Z, n - 2).prod1();
    return 0;
}