#include <stdio.h>
#include <stdint.h>
const unsigned int mod = 666013;

typedef struct {
  unsigned int m[2][2];
} matrix2x2;

matrix2x2 matrixmult2x2(matrix2x2 x, matrix2x2 y) {

  matrix2x2 r;
  r.m[0][0] = ( (uint64_t)x.m[0][0] * y.m[0][0] +
                 (uint64_t)x.m[0][1] * y.m[1][0] ) % mod;
    r.m[0][1] = ( (uint64_t)x.m[0][0] * y.m[0][1] +
                 (uint64_t)x.m[0][1] * y.m[1][1] ) % mod;
    r.m[1][0] = ( (uint64_t)x.m[1][0] * y.m[0][0] +
                 (uint64_t)x.m[1][1] * y.m[1][0] ) % mod;
    r.m[1][1] = ( (uint64_t)x.m[1][0] * y.m[0][1] +
                 (uint64_t)x.m[1][1] * y.m[1][1] ) % mod;
  return r;
}


matrix2x2 explogz(matrix2x2 a, unsigned int n) {
  matrix2x2 sol = {{{1, 0}, {0, 1}}};
  for (unsigned int i = 0; (1 << i) <= n; ++i) {

    if (((1 << i) & n) > 0)
      sol = matrixmult2x2(sol, a);

    a = matrixmult2x2(a, a);
  }
  return sol;
}

int main(void) {

  FILE *in = fopen("kfib.in", "r");
  FILE *out = fopen("kfib.out", "w");
  unsigned int n;
  if(fscanf(in, "%d", &n)!= 1) {
    return 1;
  }

  matrix2x2 a = {{{0, 1}, {1, 1}}};

  a = explogz(a, n-1);

  fprintf(out,"%d", a.m[1][1]);

  return 0;
}