#include <stdio.h>
#define MOD 666013
long long mat[2][2] = {{0, 1}, {1, 1}};
long long rezmat[2][2] = {{1, 0}, {0, 1}};;

void prod(long long m1[2][2], long long m2[2][2]){
  int i, j, k;
  long long m3[2][2];
  for(i = 0; i < 2; i++){
    for(j = 0; j < 2; j++){
      m3[i][j] = 0;
      for(k = 0; k < 2; k++){
        m3[i][j] += m1[i][k] * m2[k][j];
      }
      m3[i][j] %= MOD;
    }
  }
  for(i = 0; i < 2; i++){
    for(j = 0; j < 2; j++){
      m1[i][j] = m3[i][j];
    }
  }
}

void putere(int n){
  while(n > 0){
    if(n & 1)
      prod(rezmat, mat);
    n >>= 1;
    prod(mat, mat);
  }
}

int main(){
  FILE *in = fopen("kfib.in", "r");
  int n;
  fscanf(in, "%d", &n);
  fclose(in);
  FILE *out = fopen("kfib.out", "w");
  if(n == 0)
    fprintf(out, "0");
  else{
    n--;
    putere(n);
    fprintf(out, "%lld", rezmat[1][1]);
  }
  fclose(out);
  return 0;
}