#include<iostream>
#include<fstream>
#define mod 666013
using namespace std;
int c[2][2],t[2][2],p[2][2],vec[2][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;
ifstream intro("kfib.in"); ofstream extro("kfib.out");
int g;
intro>>g;
rid_putere(g);
inmultire_matrici(c,vec,p);
extro<<p[0][1];
intro.close(); extro.close();
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;
           }
       }  
     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";} */