#include <bits/stdc++.h>

using namespace std;

#define MOD 666013
#define int long long

template<typename T>
struct ModNumber
{
    T val;

    ModNumber() : val(0) {}
    ModNumber(const T &_val) : val((_val%MOD+MOD)%MOD) {}
    template<typename oth_t>
    ModNumber(const ModNumber<oth_t> &oth) : val(oth.val%MOD) {}

    ModNumber<T> operator+(const ModNumber<T> &oth) const {return val+oth.val;}
    ModNumber<T> operator-(const ModNumber<T> &oth) const {return val-oth.val;}
    ModNumber<T> operator*(const ModNumber<T> &oth) const {return val*oth.val;}

    ModNumber<T> &operator+=(const ModNumber<T> &oth) {val=(val+oth.val)%MOD; return *this;}
    ModNumber<T> &operator-=(const ModNumber<T> &oth) {val=(val-oth.val)%MOD; return *this;}
    ModNumber<T> &operator*=(const ModNumber<T> &oth) {val=(val*oth.val)%MOD; return *this;}

    T operator()() const {return val;}
};

typedef ModNumber<long long> modlong;

template<typename T, int l, int c>
struct mat
{
    T v[l][c];
    struct col
    {
        mat<T,l,c> *ptr; int idx;
        col(mat<T,l,c> *_p, int _i) : ptr(_p), idx(_i) {}
        T &operator[](int line) {return ptr->v[idx][line];}
    };
    col operator[](int line) {return col(this,line);}
    mat(T x=0)
    {
        for(int i=0; i<l; ++i)
            for(int j=0; j<c; ++j)
                v[i][j] = x;
    }
    mat<T,l,c> &operator=(const mat<T,l,c> &oth)
    {
        for(int i=0; i<l; ++i)
            for(int j=0; j<c; ++j)
                v[i][j] = oth.v[i][j];
        return *this;
    }
};

template<typename T, int a, int b, int c>
mat<T,a,b> operator*(const mat<T,a,c> &m1, const mat<T,c,b> &m2)
{
    mat<T,a,b> m3;
    for(int i=0; i<a; ++i)
        for(int j=0; j<b; ++j)
            for(int k=0; k<c; ++k)
                m3[i][j] += m1.v[i][k] * m2.v[k][j];
    return m3;
}

template<typename T, int s>
mat<T,s,s> pow(mat<T,s,s> x, int y)
{
    mat<T,s,s> res;
    for(int i=0; i<s; ++i) res[i][i] = 1;
    while(y>0)
    {
        if(y%2) res = res * x;
        x = x*x;
        y /= 2;
    }
    return res;
}

#define define_mat_for(sufix,type) \
typedef mat<type,1,1> mat1x1##sufix;\
typedef mat<type,1,2> mat1x2##sufix;\
typedef mat<type,1,3> mat1x3##sufix;\
typedef mat<type,1,4> mat1x4##sufix;\
typedef mat<type,2,1> mat2x1##sufix;\
typedef mat<type,2,2> mat2x2##sufix;\
typedef mat<type,2,3> mat2x3##sufix;\
typedef mat<type,2,4> mat2x4##sufix;\
typedef mat<type,3,1> mat3x1##sufix;\
typedef mat<type,3,2> mat3x2##sufix;\
typedef mat<type,3,3> mat3x3##sufix;\
typedef mat<type,3,4> mat3x4##sufix;\
typedef mat<type,4,1> mat4x1##sufix;\
typedef mat<type,4,2> mat4x2##sufix;\
typedef mat<type,4,3> mat4x3##sufix;\
typedef mat<type,4,4> mat4x4##sufix;

define_mat_for(,modlong)

signed main()
{
    ifstream fin ("kfib.in");
    ofstream fout ("kfib.out");
    ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
    long long n; fin>>n;
    mat2x2 m;
    m[0][0] = 0; m[0][1] = 1;
    m[1][0] = 1;  m[1][1] = 1;
    mat1x2 res; res[0][1] = 1;
    res = res * pow(m, n);
    fout<<res[0][0]();
    return 0;
}