#include <stdio.h>
#include <ctype.h>

// Program de Mircea Rebengiuc
// inceput pe 2021.11.12

#define MOD 666013

FILE *fin, *fout;

void mult( int mat1[2][2], int mat2[2][2] ){// mat1 *= mat2
  int i, j;
  int rez[2][2];
  
  for( i = 0 ; i < 2 ; i++ )
    for( j = 0 ; j < 2 ; j++ )
      rez[i][j] = (((long long)mat1[i][0]) * mat2[0][j] + ((long long)mat1[i][1]) * mat2[1][j]) % MOD;

  for( i = 0 ; i < 2 ; i++ )
    for( j = 0 ; j < 2 ; j++ )
      mat1[i][j] = rez[i][j];
}

int main(){
  fin  = fopen("kfib.in",  "r");
  fout = fopen("kfib.out", "w");

  int n;
  int r[2][2] = {
    { 1, 0 },
    { 0, 1 },
  };
  int a[2][2] = {
    { 0, 1 },
    { 1, 1 },
  };

  fscanf(fin, "%d\n", &n);

  while( n > 0 ){
    if( n & 1 )
      mult(r, a);

    mult(a, a);
    n >>= 1;
  }

  fprintf(fout, "%d\n", /* 0 * r[0][0] + 1 * */ r[0][1]);

  fclose(fin);
  fclose(fout);
  return 0;
}