#include <iostream>
#include <fstream>
using namespace std;
struct MatricePatratica{
long long ss, sj, ds, dj;
};

struct MatriceLiniara{
long long st, dr;
};
MatricePatratica ProdusMatricePatratica(MatricePatratica A, MatricePatratica B){
    MatricePatratica C;
C.ss=(A.ss*B.ss+A.ds*B.sj)%666013;
C.ds=(A.ss*B.ds+A.ds*B.dj)%666013;
C.sj=(A.sj*B.ss+A.dj*B.sj)%666013;
C.dj=(A.sj*B.ds+A.dj*B.dj)%666013;
return C;
}

MatricePatratica RP (MatricePatratica A, int n){
if(n==1)
    return A;
else{
    MatricePatratica mp=RP(A,n/2);
    if(n%2==0)
        return ProdusMatricePatratica(mp, mp);
    else
        return ProdusMatricePatratica(ProdusMatricePatratica(mp, mp), A);
}
}
int main()
{
    MatriceLiniara Z;
    Z.st=0;
    Z.dr=1;
    MatricePatratica A;

    A.ss=0;
    A.ds=1;
    A.sj=1;
    A.dj=1;
    //out<<"Dati n: ";
    long long n;
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
    fin>>n;
    fin.close();
    A=RP(A, n-1);

    //cout<<A.ss<<" "<<A.ds<<"\n"<<A.sj<<" "<<A.dj<<endl;
    MatriceLiniara X;
    X.st=Z.st*A.ss+Z.dr*A.sj;
    X.dr=(Z.st*A.ds+Z.dr*A.dj)%666013;

    fout<<X.dr;
    fout.close();

    return 0;
}