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

#define FILE_IN "kfib.in"
#define FILE_OUT "kfib.out"

#define MOD 666013
#define MAT_SIZE 2

// pb kfib de pe infoarena

// basically, trebuie sa gasesc termenul k din Fibo, in timp log
// problema se rezuma la putere in timp log a unei matrici ( { {0, 1}, {1, 1} } )


// algoritmul adaptat pt matrici 2*2

void alocare ( long long ret[][MAT_SIZE], long long val[][MAT_SIZE] )
{
  for ( int i = 0; i < MAT_SIZE; i++ )
    for ( int j = 0; j < MAT_SIZE; j++ )
      ret[i][j] = val[i][j];
}

void inmultire ( long long mat1[][MAT_SIZE], long long mat2[][MAT_SIZE], long long ret[][MAT_SIZE] )
{
  for ( int i = 0; i < MAT_SIZE; i++ )
    {
      for ( int j = 0; j < MAT_SIZE; j++ )
	{
	  ret[i][j] = 0LL;
	  for ( int k = 0; k < MAT_SIZE; k++ )
	    {
	      ret[i][j] += ( mat1[i][k] * mat2[k][j] );
	    }
	}
    }
}

void modulare ( long long mat[][MAT_SIZE], long long mod )
{
  for ( int i = 0; i < MAT_SIZE; i++ )
    for ( int j = 0; j < MAT_SIZE; j++ )
      if ( mat[i][j] >= mod )
	mat[i][j] %= mod;
}

void afisare ( long long mat[][MAT_SIZE] )
{
  printf ( "\n" );
  for ( int i = 0; i < MAT_SIZE; i++ )
    {
      printf ( "\t" );
      for ( int j = 0; j < MAT_SIZE; j++ )
	printf ( "%2d ", mat[i][j] );
      printf ( "\n" );
    }
  printf ( "\n" );
}

int tl_mat ( int base[][MAT_SIZE], int pow, int mod )
{
  pow -= 2;
  
  long long MM = 0LL;
  MM += mod;

  long long rez[MAT_SIZE][MAT_SIZE], acc[MAT_SIZE][MAT_SIZE], inter[MAT_SIZE][MAT_SIZE]; // inter[][] e folosita pt a retine rezultatul inmultirii

  // initializarea
  
  for ( int i = 0; i < MAT_SIZE; i++ )
    for ( int j = 0; j < MAT_SIZE; j++ )
      {
	acc[i][j] = 0LL;
	acc[i][j] += base[i][j];
	rez[i][j] = 1LL;
      }
  
  // printf ( "rez = " ); afisare ( rez );
  // printf ( "acc = " ); afisare ( acc );
  
  for ( int i = 1; i <= pow; i <<= 1 )
    {
      if ( i & pow )
	{
	  inmultire ( rez, acc, inter );
	  alocare ( rez, inter );
	  modulare ( rez, MM );
	}
      inmultire ( acc, acc, inter );
      alocare ( acc, inter );
      modulare ( acc, MM );
      /*
      printf ( "pow = %d\n", i );
      printf ( "rez = " ); afisare ( rez );
      printf ( "acc = " ); afisare ( acc );
      */
    }

  return ( int ) rez[MAT_SIZE - 1][MAT_SIZE - 1];
}

int main ( void )
{
  FILE *fin, *fout;
  fin = fopen ( FILE_IN, "r" );
  fout = fopen ( FILE_OUT, "w" );
  if ( fin == NULL || fout == NULL )
    {
      perror ( "Eroare la deschidere fisiere\n" );
      exit ( -1 );
    }

  int k;
  fscanf ( fin, "%d", &k );
  // scanf ( "%d", &k );

  int mat[MAT_SIZE][MAT_SIZE] = { {0, 1}, {1, 1} };

  int rez = tl_mat ( mat, k, MOD );

  fprintf ( fout, "%d\n", rez );
  // printf ( "%d\n", rez );
  // printf ( "%d\n", k );

  if ( ( fclose ( fin ) ) != 0 || ( fclose ( fout ) ) != 0 )
    {
      perror ( "Eroare la inchidere fisiere\n" );
      exit ( -2 );
    }

  return 0;
}