// https://infoarena.ro/problema/kfib
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

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

const int MOD = 666013;

struct Matrix {
  array<array<int, 2>, 2> mat{};
  array<int, 2>& operator[](int i) {
    return mat[i];
  }
  Matrix operator*(Matrix other) {
    Matrix ret;
    for (int i = 0; i < 2; ++i) {
      for (int k = 0; k < 2; ++k) {
        for (int j = 0; j < 2; ++j) ret[i][j] = (ret[i][j] + 1LL * mat[i][k] * other[k][j]) % MOD;
      }
    }

    return ret;
  }
};

/*void display(Matrix m) {
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) cout << m[i][j] << " ";
    cout << endl;
  }
  cout << endl;
}*/

Matrix binpow(Matrix a, int b) {
  Matrix ret = a;

  while (b) {
    if (b & 1) ret = ret * a;
    a = a * a;
    b >>= 1;
  }

  return ret;
}

int main() {
  int k;
  fin >> k;

  Matrix m;
  m[0][0] = 0;
  m[0][1] = 1;
  m[1][0] = 1;
  m[1][1] = 1;

  m = binpow(m, k);

  fout << m[0][0];
}