#include <iostream>
#include <fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
#define mod 666013;
int M[3][3],MZ[3][3],S[3][3];
inline void inmult(int A[][3], int B[][3], int C[][3])
{
    int i,j,k;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            for(k=0;k<2;k++)
                C[i][j]=(C[i][j]+1LL*A[i][k]*B[k][j])%mod;

}
inline void cpy(int A[][3], int B[][3])
{for(int i=0;i<2;i++)
  for(int j=0;j<2;j++)
   A[i][j]=B[i][j];
}
void pow(long long p,int N[][3])
{
    int C[3][3], AUX[3][3], i;
    cpy(C,M);
    N[0][0]=N[1][1]=1;
    for(i=0;(1<<i)<=p;i++)
    {
     if(p&(1<<i))
        {
            cpy(AUX,MZ);
            inmult(N, C, AUX);
            cpy(N, AUX);
        }

        cpy(AUX,MZ);
        inmult(C,C,AUX);
        cpy(C,AUX);
    }
}
int main()
{
    long long k;
    f>>k;
    k--;
    MZ[0][0]=0;
    M[0][1]=M[1][1]=M[1][0]=1;
    MZ[0][0]=MZ[1][0]=MZ[0][1]=MZ[0][0]=0;
    pow(k,S);
    g<<S[1][1];
}