#include <bits/stdc++.h>
using namespace std;

struct Matrix{
    unsigned long long a, b, c, d;

    Matrix(unsigned long long A , unsigned long long B, unsigned long long C, unsigned long long D)
    :a{A}, b{B}, c{C}, d{D} {

    }

    Matrix operator *(Matrix& X){
        Matrix answer(1, 1, 1, 0);

        answer.a = (1LL*a*X.a + 1LL*b*X.c)%666013;
        answer.b = (1LL*a*X.b + 1LL*b*X.d)%666013;
        answer.c = (1LL*c*X.a + 1LL*d*X.c)%666013;
        answer.d = (1LL*c*X.b + 1LL*d*X.d)%666013;

        return answer;
    }
};

Matrix power(Matrix& X, unsigned long long N){
    if(N == 0){
        Matrix temp(1, 0, 0, 1);
        return temp;
    }

    if(N == 1){
        Matrix temp(1, 1, 1, 0);
        return temp;
    }

    X = power(X, N/2);
    X = X * X;

    if(N & 1) {
        Matrix temp(1, 1, 1, 0);
        X = X * temp;
    }

    return X;
}

ifstream fin("kfib.in");
ofstream fout("kfib.out");

int main()
{
    unsigned long long N;

    fin>>N;

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

    Matrix X(1, 1, 1, 0);

    X = power(X, N - 1);

    fout<<X.a;
}