#include <iostream>
#include <fstream>

using namespace std;

void inmultire (int a[2][2])
{
      int i,j,k;
      int c[2][2]={0};
               for (i = 0 ; i < 2; i++)
                   for ( j = 0 ; j< 2; j++)
                       for ( k = 0; k <2 ;k++)
                       c[i][j] = (c[i][j] + a[i][k]* a[k][j]) % 666013;
                for (i = 0 ; i < 2; i++)
                   for ( j = 0 ; j< 2; j++)
                   a[i][j] = c[i][j];        
 }

void putere( int ma[2][2],int mb[2][2],long  p  )
{
     if ( p == 1 ) 
         return;
     else if ( p % 2 == 0 ) 
          {
              inmultire(ma);
              putere(ma,mb,p/2);
          }
          else 
          {
            mb[0][0] = ma[0][0];
            mb[0][1] = ma[0][1];
            mb[1][0] = ma[1][0];
            mb[1][1] = ma[1][1];
            inmultire (ma);
            putere(ma,mb, (p-1)/2);
            int mc[2][2]={0};
            int i,j,k;
            for (i = 0 ; i < 2; i++)
                   for ( j = 0 ; j< 2; j++)
                       for ( k = 0; k <2 ;k++)
                       mc[i][j] = (mc[i][j] +  ma[i][k]* mb[k][j]) % 666013;
              
             for (i = 0 ; i < 2; i++)
                   for ( j = 0 ; j< 2; j++)
                   ma[i][j] = mc[i][j];         
           }
}

int main()
{

    ifstream in("kfib.in");
    ofstream out("kfib.out");
    long k;
    in>>k;
    int matrix[2][2], matrice[2][2];
    matrix[0][0] = matrice[0][0]= 1;
    matrix[0][1] = matrice[0][1]= 1;
    matrix[1][0] = matrice[1][0]= 1;
    matrix[1][1] = matrice[1][1]= 0;
    putere(matrix,matrice,k-1);
    out<<matrix[0][0];
    in.close();
    out.close();
    return 0;
}