#include <cstdio>
#include <vector>
#include <fstream>
#include <iostream>
using namespace std;

template <typename T>
class Matrix{
public:
  Matrix(int n, int m): rows_(n), cols_(m), data_(n, vector<T>(m)) {}
  Matrix(vector<vector<T>> other) {
    rows_ = other.size();
    if (rows_)
      cols_ = other[0].size();
    else
      cols_ = 0;
    data_.resize(numRows(), vector<T>(numCols(), 0));
    for (int i = 0; i < numRows(); ++i)
      for (int j = 0; j < numCols(); ++j)
	set(i, j, other[i][j]);
  }
  void set(int x, int y, int val) {
    data_[x][y] = val;
  }
  const T& get(int x, int y) const {
    return data_[x][y];
  }
  int numRows() const {
    return rows_;
  }
  int numCols() const {
    return cols_;
  }
  Matrix operator + (const Matrix& other) const{
    Matrix answer(numRows(), numCols());
    for (int i = 0; i < numRows(); ++i)
      for (int j = 0; j < numCols(); ++j)
	answer.set(i, j, (get(i, j) + other.get(i, j)) % MOD);
    return answer;
  }
  Matrix operator * (const Matrix& other) const{
    Matrix answer(numRows(), other.numCols());
    for (int i = 0; i < numRows(); ++i)
      for (int j = 0; j < other.numCols(); ++j)
	for (int k = 0; k < numCols(); ++k)
	  answer.set(i, j, (1LL*answer.get(i,j) + (1LL * get(i,k)) * (1LL * other.get(k,j))) % MOD);
    return answer;
  }
  static Matrix ID(int k) {
    Matrix answer(k, k);
    for (int i = 0; i < k; ++i)
      answer.set(i, i, 1);
    return answer;
  }
  friend ostream& operator << (ostream&out, Matrix& other) {
    for (int i = 0; i < other.numRows(); ++i) {
      for (int j = 0; j < other.numCols(); ++j)
	out << other.get(i, j) << " ";
      out << "\n";
    }
    return out;
  }
private:
  vector<vector<T>> data_;
  int rows_;
  int cols_;
  static const int MOD = 666013;
};

template <typename T>
Matrix<T> lg_put(Matrix<T> A, int K) {
  if (K == 0)
    return Matrix<T>::ID(A.numRows());
  if (K == 1)
    return A;
  if (K & 1)
    return A * lg_put(A * A, K >> 1);
  else
    return lg_put(A * A, K >> 1);
}

int main()
{
  freopen("kfib.in", "r", stdin);
  freopen("kfib.out", "w", stdout);
  
  Matrix<int> A({{1,1}, {1,0}});
  Matrix<int> B(2,1); B.set(0, 0, 1); B.set(1, 0, 0);

  int K;
  scanf("%d", &K);
  if (K == 0) {
    printf("%d\n", 0);
    return 0;
  }
  if (K == 1 || K == 2) {
    printf("%d\n", 1);
    return 0;
  }
  
  Matrix<int> C = lg_put<int>(A, K);
  printf("%d\n", C.get(0,1));
  return 0;
}