#include <iostream>
#include <fstream>
#include <initializer_list>
#include <vector>

using namespace std;

#define mod 666013

struct vec2{
private:
    long long data[2]={0, 0};

public:
    long long& operator[](int i){
        return this->data[i];
    }

    const long long& operator[](int i) const{
        return this->data[i];
    }

    vec2()=default;

    vec2(initializer_list<long long> init_list){
        for(int i=0; i<2; i++){
            this->data[i]=*(init_list.begin()+i);
        }
    }
};

struct mat2x2{
private:
    long long data[2][2]={{0, 0}, {0, 0}};

public:
    long long* operator[](int i){
        return this->data[i];
    }

    const long long* operator[](int i) const{
        return this->data[i];
    }

    mat2x2()=default;

    mat2x2(initializer_list<initializer_list<long long>> init_list){
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                this->data[i][j]=*((init_list.begin()+i)->begin()+j);
            }
        }
    }

    mat2x2(const mat2x2& m){
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                this->data[i][j]=m[i][j];
            }
        }
    }

    mat2x2 operator=(const mat2x2& M){
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                this->data[i][j]=M[i][j];
            }
        }

        return *this;
    }

    friend mat2x2 operator*(const mat2x2& A, const mat2x2& B){
        mat2x2 C;

        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                for(int k=0; k<2; k++){
                    C[i][j]=(C[i][j]+A[i][k]*B[k][j]%mod)%mod;
                }
            }
        }

        return C;
    }

    friend vec2 operator*(const mat2x2& M, const vec2& v){
        vec2 u;

        for(int i=0; i<2; i++){
            for(int k=0; k<2; k++){
                u[i]=(u[i]+M[i][k]*v[k]%mod)%mod;
            }
        }

        return u;
    }
};

#define I mat2x2({{1, 0}, {0, 1}})

mat2x2 log_pow(const mat2x2& A, int n){
    if(n==0) return I;

    mat2x2 B=log_pow(A, n/2);

    if(n%2==0){
        return B*B;
    }else{
        return B*B*A;
    }
}

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

    int n; fin>>n;

    mat2x2 F={{1, 1}, {1, 0}}; vec2 f1={1, 0};

    vec2 fn=log_pow(F, n-1)*f1;

    fout<<fn[0];

    return 0;
}