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

#define MOD 666013

typedef struct {
  long long a[2][2];
} mat_s;

mat_s mat_multiply(mat_s a, mat_s b){
  mat_s result = {{{0}}};
  for(int i = 0; i < 2; i++){
    for(int j = 0; j < 2; j++){
      for(int k = 0; k < 2; k++){
        result.a[i][j] = (result.a[i][j] + a.a[i][k] * b.a[k][j]) % MOD;
      }
    }
  }
  return result;
}

mat_s mat_pow(mat_s base, long long exp){
  mat_s result = {{
    {1, 0},
    {0, 1}
  }};
  while(exp > 0){
    if(exp % 2 == 1){
      result = mat_multiply(result, base);
    }
    base = mat_multiply(base, base);
    exp /= 2;
  }
  return result;
}

long long kfib(long long k){
  if(k == 0) return 0;
  if(k == 1) return 1;

  mat_s base = {{
    {0, 1},
    {1, 1}
  }};

  mat_s res = mat_pow(base, k - 1);
  return res.a[1][1] % MOD;
}

int main(void){
  FILE *fin = NULL;
  FILE *fout = NULL;

  fin = fopen("kfib.in", "r");
  if(fin == NULL){
    perror("kfib.in");
    return 1;
  }

  fout = fopen("kfib.out", "w");
  if(fout == NULL){
    perror("kfib.out");
    fclose(fin);
    return 1;
  }

  long long k = 0;
  fscanf(fin, "%lld", &k);

  fprintf(fout, "%lld\n", kfib(k));

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