#include <fstream>

#define MOD 666013

using namespace std;

ifstream in;
ofstream out;

long long w[2][2],z[2][2];

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

    c[0][0]=((a[0][0]*b[0][0])%MOD+(a[0][1]*b[1][0])%MOD)%MOD;
    c[0][1]=((a[0][0]*b[0][1])%MOD+(a[0][1]*b[1][1])%MOD)%MOD;
    c[1][0]=((a[1][0]*b[0][0])%MOD+(a[1][1]*b[1][0])%MOD)%MOD;
    c[1][1]=((a[1][0]*b[0][1])%MOD+(a[1][1]*b[1][1])%MOD)%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-=2;

    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;
}