#include <cstdio>

#define MOD 666013

int m[2][2];

void mulcop(int a[2][2], int b[2][2]) {
  int aux[2][2];
  aux[0][0] = aux[1][0] = aux[0][1] = aux[1][1] = 0;
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      for (int k = 0; k < 2; ++k) {
        aux[i][j] = (aux[i][j] + 1LL * a[i][k] * b[k][j]) % MOD;
      }
    }
  }
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      a[i][j] = aux[i][j];
    }
  }
}

void pow(int n) {
  int p[2][2];
  p[1][0] = p[0][1] = p[1][1] = 1;
  p[0][0] = 0;
  m[0][0] = m[1][1] = 1;
  while (n > 0) {
    if (n & 1) {
      mulcop(m, p);
    }
    mulcop(p, p);
    n >>= 1;
  }
}

int main() {
  int n;
  FILE *f = fopen("kfib.in", "r");
  fscanf(f, "%d", &n);
  fclose(f);
  pow(n - 1);
  f = fopen("kfib.out", "w");
  fprintf(f, "%d\n", m[1][1]);
  fclose(f);
  return 0;
}