#include <fstream>
#define MOD 666013

using namespace std;

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

int N;

//generati al n-lea numar fibonacci % 666001

struct Matrice
{
       long long  a,b,c,d;
};

Matrice Unit;


Matrice Inmulteste(Matrice M1, Matrice M2)
{
        Matrice M3;
        M3.a =  ((M1.a*M2.a)%MOD + (M1.b*M2.c)%MOD)%MOD;
        M3.b =  ((M1.a*M2.b)%MOD + (M1.b*M2.d)%MOD)%MOD;
        M3.c =  ((M1.c*M2.a)%MOD + (M1.d*M2.c)%MOD)%MOD;
        M3.d =  ((M1.c*M2.b)%MOD + (M1.d*M2.d)%MOD)%MOD;
        return M3;
}

Matrice Putere(int N)
{
    if(N==1)return Unit;
    Matrice Aux,Ok;
    Aux = Putere(N/2);
    Ok = Inmulteste(Aux,Aux);
    Ok.a %=MOD;
    Ok.b %=MOD;
    Ok.c %=MOD;
    Ok.d %=MOD;
    if(N&1)
           Ok = Inmulteste(Ok,Unit);
    Ok.a %=MOD;
    Ok.b %=MOD;
    Ok.c %=MOD;
    Ok.d %=MOD;
    return Ok;
}

int main ()
{
    in>>N;
    Unit.a = Unit.b = Unit.c = 1,Unit.d = 0;
    Unit = Putere(N-1);
    out<<Unit.a%MOD;
    return 0;
}