#include <fstream>

using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
const int MOD=666013;
int n;
struct mat
{
    int m[2][2];
}a,aux;
mat inmultire(mat x,mat y)
{
    mat man;
    man.m[0][0]=(x.m[0][0]*y.m[0][0]%MOD+x.m[0][1]*y.m[1][0]%MOD)%MOD;
    man.m[0][1]=(x.m[0][0]*y.m[0][1]%MOD+x.m[0][1]*y.m[1][1]%MOD)%MOD;
    man.m[1][0]=(x.m[1][0]*y.m[0][0]%MOD+x.m[1][1]*y.m[1][0]%MOD)%MOD;
    man.m[1][1]=(x.m[1][0]*y.m[0][1]%MOD+x.m[1][1]*y.m[1][1]%MOD)%MOD;
    return  man;
}
void init();

int main()
{
    in>>n;
    init();
    int k=0;
    while((1<<k)<=n)
    {
        if((1<<k)&n)
            aux=inmultire(aux,a);
        k++;
        a=inmultire(a,a);
    }
    out<<aux.m[0][1];
    return 0;
}

void init()
{
    a.m[0][0]=aux.m[0][0]=1;
    a.m[0][1]=1;
    a.m[1][0]=1;
    a.m[1][1]=0;
    aux.m[0][1]=0;
    aux.m[1][0]=0;
    aux.m[1][1]=1;
}