#include <iostream>
#include <fstream>

const int MOD = 666013;

class Matrix {
public:
  int n, m;
  int **data;

  Matrix(int n, int m) {
    this->n = n;
    this->m = m;

    this->data = new int*[n];
    this->data[0] = new int[n * m];
    for (int i = 1; i < n; ++i)
      this->data[i] = this->data[i - 1] + m;
  }

  Matrix (const Matrix& other) {
    this->n = other.n;
    this->m = other.m;

    this->data = new int*[n];
    this->data[0] = new int[n * m];
    for (int i = 1; i < n; ++i)
      this->data[i] = this->data[i - 1] + m;

    for (int i = 0; i < this->n; ++i) {
      for (int j = 0; j < this->m; ++j)
        this->data[i][j] = other.data[i][j];
    }
  }

  ~Matrix() {
    delete[] this->data[0];
    delete[] this->data;
  }

  Matrix operator = (const Matrix& other) {
    for (int i = 0; i < this->n; ++i) {
      for (int j = 0; j < this->m; ++j)
        this->data[i][j] = other.data[i][j];
    }

    return *this;
  }

  Matrix operator * (const Matrix& other) const {
    Matrix ans(this->n, other.m);

    for (int i = 0; i < this->n; ++i) {
      for (int j = 0; j < other.m; ++j) {
        ans.data[i][j] = 0;

        for (int k = 0; k < this->m; ++k)
          ans.data[i][j] = (int)((ans.data[i][j] + ((int64_t)this->data[i][k] * other.data[k][j])) % MOD);
      }
    }

    return ans;
  }

  Matrix operator ^ (int exp) const {
    Matrix ans = Matrix::makeIdentity(this->n);
    Matrix base(*this);

    while (exp) {
      if ((exp & 1) != 0)
        ans = ans * base;

      exp >>= 1;
      base = base * base;
    }

    return ans;
  }

  static Matrix makeIdentity(int n) {
    Matrix I(n, n);

    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j)
        I.data[i][j] = 0;

      I.data[i][i] = 1;
    }

    return I;
  }
};

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

  int k;
  in >> k;

  Matrix fib(2, 2);
  fib.data[0][0] = 0;
  fib.data[0][1] = fib.data[1][0] = fib.data[1][1] = 1;

  Matrix start(1, 2);
  start.data[0][0] = start.data[0][1] = 1;

  --k;
  start = start * (fib ^ k);

  out << start.data[0][0] << '\n';

  return 0;
}