#include<iostream>
#include<fstream>
#define mod 666013
using namespace std;
int c[2][2],t[2][2],p[2][2],vec[2][2];
void copie(int a[][2], int r[][2]);
void inmultire_matrici(int a[][2], int b[][2], int r[][2]);
void rid_putere(int n);
int main(){
t[1][1]=c[1][1]=1; t[0][1]=c[0][1]=1; 
t[1][0]=c[1][0]=1; t[0][0]=c[0][0]=0;    
vec[0][1]=1; int rez[2][2];
ifstream intro("kfib.in"); ofstream extro("kfib.out");
int g;
intro>>g;
//cin>>g;
if (g==0) cout<<0; else
{rid_putere(g);
inmultire_matrici(vec,p,rez);
extro<<rez[0][0];
//cout<<rez[0][0]; 
intro.close(); extro.close();
}
//cin.ignore(2);
return(0);
    }

void inmultire_matrici(int a[][2], int b[][2], int r[][2])
 {
   int s;
   for (int i=0; i<2; i++) 
      {
       for (int j=0; j<2; j++)
          {
           s=0;
           for (int k=0; k<2; k++){
               s=s+a[i][k]*b[k][j];}
           r[i][j]=s%mod;
           }
       }  
    
     }
void rid_putere(int n)
{
  if(n!=0){
     if(n==1) { inmultire_matrici(c,t,p); copie(c,p); }
     else
     if(n%2==0) { inmultire_matrici(c,c,p); copie(c,p); rid_putere(n/2);}
     else 
     if(n%2==1) { inmultire_matrici(c,c,p); copie(c,p); rid_putere((n-1)/2);}      
           }   
     }
void copie(int a[][2], int r[][2])
{  a[0][0]=r[0][0]; a[1][0]=r[1][0];
   a[0][1]=r[0][1]; a[1][1]=r[1][1];}

/*void rid_putere(int n)
{ for (int i=1; i<=n; i++)
{ inmultire_matrici(c,t,p);}} */
/*for (int i=0; i<2; i++) {
    for (int j=0; j<2; j++)
    { cout<<c[i][j]<<"  ";}
    cout<<"\n";} */