#include <fstream>

struct FibMatrix{
    size_t el[2][2];

    FibMatrix operator * (FibMatrix const& A){
        FibMatrix C;
        C.el[0][0] = (1LL * el[0][0] * A.el[0][0] % 666013 + 1LL * el[0][1] * A.el[1][0] % 666013) % 666013;
        C.el[0][1] = (1LL * el[0][0] * A.el[0][1] % 666013 + 1LL * el[0][1] * A.el[1][1] % 666013) % 666013;
        C.el[1][0] = (1LL * el[1][0] * A.el[0][0] % 666013 + 1LL * el[1][1] * A.el[0][1] % 666013) % 666013;
        C.el[1][1] = (1LL * el[1][0] * A.el[0][1] % 666013 + 1LL * el[1][1] * A.el[1][1] % 666013) % 666013;

        return C;
    }

};

FibMatrix identity;

FibMatrix lgput(FibMatrix A, size_t N){
    if(N == 1) return A;
    if(N == 0) return identity;

    return lgput(A, N / 2) * lgput(A, N / 2) * lgput(A, N % 2);
}


int main()
{
    std::ifstream fin("kfib.in");
    std::ofstream fout("kfib.out");

    size_t K;

    fin >> K;

    if(K == 0){
        fout << 0;
        return 0;
    }

    if(K == 1 || K == 2){
        fout << 1;
        return 0;
    }

    identity.el[0][0] = 1;
    identity.el[0][1] = 0;
    identity.el[1][0] = 0;
    identity.el[1][1] = 1;

    FibMatrix A;
    A.el[0][0] = 1;
    A.el[0][1] = 1;
    A.el[1][0] = 1;
    A.el[1][1] = 0;

    A = lgput(A, K - 2);

    fout << (1LL*A.el[0][0] + 1LL*A.el[0][1])% 666013;
}