#include <fstream>

#define MOD 666013

using namespace std;

ifstream in;
ofstream out;

int w[2][2],z[2][2];

inline void mul(int a[][2],int b[][2])
{
    int c[2][2];

    c[0][0]=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%MOD;
    c[0][1]=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%MOD;
    c[1][0]=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%MOD;
    c[1][1]=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%MOD;

    a[0][0]=c[0][0];
    a[0][1]=c[0][1];
    a[1][0]=c[1][0];
    a[1][1]=c[1][1];
}

int main()
{
    int N;

    in.open("kfib.in");

    in>>N;
    --N;

    in.close();

    w[0][0]=0;
    w[0][1]=1;
    w[1][0]=1;
    w[1][1]=1;

    z[0][0]=1;
    z[0][1]=0;
    z[1][0]=0;
    z[1][1]=1;

    for(int pow=1;pow<=N;pow<<=1)
    {
        if(N&pow) mul(z,w);
        mul(w,w);
    }

    out.open("kfib.out");

    out<<(z[0][1]+z[1][1])%MOD<<'\n';

    out.close();

    return 0;
}