#include <iostream>
#include <fstream>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

#define modulo 666013

struct fibo_mat{
    long long elems[3][3] = {{0,1},{1,1}};

    fibo_mat multiply( fibo_mat x, fibo_mat y ){
        fibo_mat z;
        z.elems[0][0] = (x.elems[0][0] * y.elems[0][0] + x.elems[0][1] * y.elems[1][0])%modulo;
        z.elems[0][1] = (x.elems[0][0] * y.elems[0][1] + x.elems[0][1] * y.elems[1][1])%modulo;
        z.elems[1][0] = (x.elems[1][0] * y.elems[0][0] + x.elems[1][1] * y.elems[1][0])%modulo;
        z.elems[1][1] = (x.elems[1][0] * y.elems[0][1] + x.elems[1][1] * y.elems[1][1])%modulo;
        return z;
    }

};

fibo_mat power(fibo_mat& m, long x ){
    fibo_mat r, m_cpy;
    while(x){
        if(x % 2 != 0)
            m = m.multiply(r,m);
     r = r.multiply(r,r);
     x/=2;
     }
     return r;
}

int main()
{
    fibo_mat m;
    long x;
    f>>x;
    power(m,x);
    g<<m.elems[0][0]%modulo;
}