#include <fstream>
#include <vector>

#include <iostream>

using namespace std;

template <typename T>
using Matrix = vector<vector<T>>;

constexpr int kMod = 666013;
const Matrix<int> kOne = {{1, 0}, {0, 1}};

Matrix<int> operator*(const Matrix<int> &a, const Matrix<int> &b)
{
  if (a[0].size() != b.size()) {
    return Matrix<int>();
  }

  Matrix<int> res(a.size(), vector<int>(b[0].size(), 0));
  for (size_t i = 0; i < res.size(); ++i) {
    for (size_t j = 0; j < res[0].size(); ++j) {
      for (size_t k = 0; k < a[0].size(); ++k) {
        res[i][j] += 1LL * a[i][k] * b[k][j] % kMod;
        res[i][j] %= kMod;
      }
    }
  }
  return res;
}

Matrix<int> Power(const Matrix<int> &base, int exp)
{
  if (exp == 0) {
    return kOne;
  } else if (exp == 1) {
    return base;
  }

  if (exp % 2 == 0) {
    auto root = Power(base, exp / 2);
    return root * root;
  }
  return base * Power(base, exp - 1);
}

int KFibo(int n)
{
  if (n == 0) {
    return 0;
  }

  auto mat = Power({{0, 1}, {1, 1}}, n - 1);
  mat = mat * Matrix<int>{{0}, {1}};
  return mat.back().back() % kMod;
}

int main()
{
  ifstream fin("kfib.in");
  ofstream fout("kfib.out");

  int n;
  fin >> n;

  auto res = KFibo(n);
  fout << res << "\n";

  return 0;
}