#include <fstream>
using namespace std;

#define MOD 666013

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

typedef long long** matrice;

int n;

matrice I;

void aloc(matrice &M)
{
    M = new long long*[2];
    M[0] = new long long[2];
    M[1] = new long long[2];
}

matrice inmult(matrice A, matrice B)
{
    matrice R;
    aloc(R);

    R[0][0] = A[0][0]*B[0][0] + A[0][1]*B[1][0];
    R[0][1] = A[0][0]*B[0][1] + A[0][1]*B[1][1];
    R[1][0] = A[1][0]*B[0][0] + A[1][1]*B[1][0];
    R[1][1] = A[1][0]*B[0][1] + A[1][1]*B[1][1];

    for(int i=0;i<=1;++i) for(int j=0;j<=1;++j) R[i][j] %= MOD;

    return R;
}

matrice put(matrice A, int p)
{
    if(p==0) return I;

    matrice R = put(A, p>>1);
    R = inmult(R, R);
    if(p&1) R = inmult(R, A);
    return R;
}

int main()
{
    f>>n;

    aloc(I);
    I[0][0] = I[1][1] = 1;
    I[0][1] = I[1][0] = 0;

    matrice M;
    aloc(M);
    M[0][0] = 0;
    M[0][1] = M[1][0] = M[1][1] = 1;

    matrice R = put(M, n);
    g<<R[1][0]<<"\n";

    f.close();
    g.close();
    return 0;
}