#include <stdio.h>
#include <stdlib.h>

int Z[2][2] = {{0, 1},{1, 1}};


int exp_log(int Z[2][2], int n)
{
  int A[2][2];
  if(n == 0)
    {
      return 0;
    }

  if(n == 1)
    {
      return 1;
    }
 
  if(n % 2 == 0)
    {
      //A = Z*Z
      A[0][0] = (Z[0][0] * Z[0][0] + Z[0][1] * Z[1][0])%666013;
      A[0][1] = (Z[0][0] * Z[0][1] + Z[0][1] * Z[1][1])%666013;
      A[1][0] = (Z[1][0] * Z[0][0] + Z[1][1] * Z[1][0])%666013;
      A[1][1] = (Z[1][0] * Z[0][1] + Z[1][1] * Z[1][1])%666013;
      return exp_log(A, n/2);
    }
 
  else // if(n % 2 == 1)
    {
      //A = Z*Z
      A[0][0] = (Z[0][0] * Z[0][0] + Z[0][1] * Z[1][0])%666013;
      A[0][1] = (Z[0][0] * Z[0][1] + Z[0][1] * Z[1][1])%666013;
      A[1][0] = (Z[1][0] * Z[0][0] + Z[1][1] * Z[1][0])%666013;
      A[1][1] = (Z[1][0] * Z[0][1] + Z[1][1] * Z[1][1])%666013;
      
      
      /* return  |x *| */ exp_log(A, n/2);
      
      //Z * A
      A[0][0] = (Z[0][0] * A[0][0] + Z[0][1] * A[1][0])%666013;
      A[0][1] = (Z[0][0] * A[0][1] + Z[0][1] * A[1][1])%666013;
      A[1][0] = (Z[1][0] * A[0][0] + Z[1][1] * A[1][0])%666013;
      A[1][1] = (Z[1][0] * A[0][1] + Z[1][1] * A[1][1])%666013;

      return 0*A[0][1] + 1*A[1][1];
      // M(n) = M(1) * Z^(n-1);
      // M(1) = (0,1);
    }
  
}

int main()
{
  int k = 0;

  int al_k_lea_termen = 0;

  
  FILE *file_in = NULL;
  FILE * file_out = NULL;

  if((file_in = fopen("kfib.in","r")) == NULL)
    {
      perror("EROARE LA DESCHIDEREA FISIERULUI DE CITIRE !");
      exit(-1);
    }

  if((file_out = fopen("kfib.out","w")) == NULL)
    {
      perror("EROARE LA DESCHIDEREA FISIERULUI DE SCRIERE !");
      exit(-1);
    }

  fscanf(file_in,"%d",&k);

  al_k_lea_termen = exp_log(Z,k);

  fprintf(file_out,"%d",al_k_lea_termen);

  fclose(file_in);

  fclose(file_out);

  return 0;
}