#include <fstream>
#define mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long k;
struct matrice
{
    int poz11,poz12,poz21,poz22;
};
matrice mat1,mat2,mat3,unitate,a,b;
matrice inmultire(matrice mat1, matrice mat2)
{
    mat3.poz11=(1LL*mat1.poz11*mat2.poz11)%mod+(1LL*mat1.poz12*mat2.poz21)%mod;
    mat3.poz12=(1LL*mat1.poz11*mat2.poz12)%mod+(1LL*mat1.poz12*mat2.poz22)%mod;
    mat3.poz21=(1LL*mat1.poz21*mat2.poz11)%mod+(1LL*mat1.poz22*mat2.poz21)%mod;
    mat3.poz22=(1LL*mat1.poz21*mat2.poz12)%mod+(1LL*mat1.poz22*mat2.poz22)%mod;
    return mat3;
}
matrice putere(long long p)
{
    if(p==0)
        return unitate;
    else
    {
        matrice aux=putere(p/2);
        aux=inmultire(aux,aux);
        if(p&1)
            aux=inmultire(mat1,aux);
        return aux;
    }
}
int main()
{
    f>>k;
    unitate.poz11=1;
    unitate.poz22=1;
    mat2.poz11=0;
    mat2.poz21=1;
    mat1.poz12=1;
    mat1.poz21=1;
    mat1.poz22=1;
    a=putere(k-1);
    b=inmultire(a,mat2);
    g<<b.poz21;
    return 0;
}