#include <iostream>
#include <fstream>
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
int mat[3][3],fib[3][3];
#define MOD 666013
inline void mul(int a[3][3],int b[3][3],int c[3][3])
{   int i,j,k;

     for(i=1;i<=2;i++)
         for(j=1;j<=2;j++)
           {  c[i][j]=0;
               for(k=1;k<=2;k++)
             c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%MOD;}
}
inline void exp(int mat[3][3],int pu)
{  if(pu<=1)return;
    int aux[3][3],c[3][3];
    aux[1][1]=aux[1][2]=aux[2][1]=1;
    aux[2][2]=0;
    exp(mat,pu/2);
    mul(mat,mat,c);
    mat[1][1]=c[1][1];
    mat[1][2]=c[1][2];
    mat[2][1]=c[2][1];
    mat[2][2]=c[2][2];
    if(pu%2)mul(mat,aux,c);
    {mat[1][1]=c[1][1];
    mat[1][2]=c[1][2];
    mat[2][1]=c[2][1];
    mat[2][2]=c[2][2];}
}

int main()
{   int n,k,i;
   in>>k;
     mat[1][1]=mat[2][1]=mat[1][2]=1;
    exp(mat,k-1);
    out<<mat[1][1];

    return 0;
}