#include <fstream>
#define MOD 6660001

using namespace std;

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

int N;

//generati al n-lea numar fibonacci % 666001

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

Matrice Unit;


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

Matrice Putere(int N)
{
    if(N==1)return Unit;
    Matrice Aux,Ok;
    Aux = Putere(N/2);
    Ok = Inmulteste(Aux,Aux);
    if(N&1)
           Ok = Inmulteste(Ok,Unit);
    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;
}