#include <array>
#include <fstream>

#define MODULO 666013
typedef std::array<std::array<long long, 2>, 2> ARR;

ARR matrixMultiply(ARR m, ARR n) {
  ARR nm;
  nm[0][0] = (((m[0][0] % MODULO) * (n[0][0] % MODULO)) % MODULO + ((m[0][1] % MODULO) * (n[1][0] % MODULO)) % MODULO) % MODULO;
  nm[0][1] = (((m[0][0] % MODULO) * (n[0][1] % MODULO)) % MODULO + ((m[0][1] % MODULO) * (n[1][1] % MODULO)) % MODULO) % MODULO;
  nm[1][0] = (((m[1][0] % MODULO) * (n[0][0] % MODULO)) % MODULO + ((m[1][1] % MODULO) * (n[1][0] % MODULO)) % MODULO) % MODULO;
  nm[1][1] = (((m[1][0] % MODULO) * (n[0][1] % MODULO)) % MODULO + ((m[1][1] % MODULO) * (n[1][1] % MODULO)) % MODULO) % MODULO;
  return nm;
}

ARR matrixPower(ARR m, unsigned power) {
  if (power == 1) return m;
  if (power % 2 == 0) {
    return matrixPower(matrixMultiply(m, m), power / 2);
  } else {
    return matrixMultiply(m, matrixPower(m, power - 1));
  }
}

int main() {
  std::ifstream in("kfib.in");
  std::ofstream out("kfib.out");

  long long k;
  in >> k;
  if (k == 0) {
    out << 0 << "\n";
    return 0;
  }
  if (k == 1) {
    out << 1 << "\n";
    return 0;
  }

  ARR a;
  a[0][0] = 0;
  a[0][1] = 1;
  a[1][0] = 1;
  a[1][1] = 1;

  a = matrixPower(a, k - 1);
  out << a[1][1] << "\n";
  return 0;
}