#include <fstream>

const unsigned MODULO=666013;

class M22{
    public:
        unsigned a11,a12,a21,a22;
        M22(){a11=1;a12=0;a21=0;a22=1;}
        M22(unsigned a,unsigned b,unsigned c,unsigned d){a11=a;a12=b;a21=c;a22=d;}
        M22 operator=(const M22 &what){ a11=what.a11; a12=what.a12; a21=what.a21; a22=what.a22; return *this;}
        M22 operator*=(const M22 what){
            unsigned long long a,b,c,d;
            a=static_cast<long long>(a11)*what.a11+static_cast<long long>(a12)*what.a21;
            b=static_cast<long long>(a11)*what.a12+static_cast<long long>(a12)*what.a22;
            c=static_cast<long long>(a21)*what.a11+static_cast<long long>(a22)*what.a21;
            d=static_cast<long long>(a21)*what.a21+static_cast<long long>(a22)*what.a22;
            a11=a%MODULO; a12=b%MODULO; a21=c%MODULO; a22=d%MODULO;
            return *this;
        }
};

M22 exp(M22 x, unsigned k){
    if(k==0) return M22();
    else if(k==1) return x;
    else{
        M22 y=exp(x,k>>1);
        y*=y;
        if(k&1) y*=x;
        return y;
    }
}

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

    unsigned k; fin>>k;
    if(k==0) fout<<"0\n";
    else if(k==1) fout<<"1\n";
    else{
        --k;
        M22 z(0,1,1,1);
        fout<<exp(z,k).a22<<'\n';
    }
}