#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
void copie(long long a[2][2], long long b[2][2])
{
    a[0][0]=b[0][0];
    a[0][1]=b[0][1];
    a[1][0]=b[1][0];
    a[1][1]=b[1][1];
}
    void produs(long long a[2][2],long long b[2][2],long long c[2][2])
{
    c[0][0]=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%666013;
    c[0][1]=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%666013;
    c[1][0]=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%666013;
    c[1][1]=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%666013;
}
long long E,P[2][2],X[2][2],Q[2][2],Y[2][2],A[2][2],k,i;
int main()
{
    fin>>k;
    E=k-1;
    A[0][0]=0;
    A[0][1]=1;
    A[1][1]=1;
    A[1][0]=1;
    copie(X,A);
    P[0][0]=1;
    P[1][1]=1;
    while(E>0)
    {
        if(E%2==1)
        {
            produs(P,X,Q);
            copie(P,Q);
        }
        produs(X,X,Y);
        copie(X,Y);
        E=E/2;
    }
    fout<<P[1][1];
    return 0;
}