#include <bits/stdc++.h>

using namespace std;

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

using ll = long long;

const int mod = 666013;

int n;

class Matrix {
private:
  int m[2][2];
public:
  Matrix(int _x, int _y, int _z, int _w) {
    m[0][0] = _x;
    m[0][1] = _y;
    m[1][0] = _z;
    m[1][1] = _w;
  }
  Matrix operator* (const Matrix& snd) {
    Matrix ans(0, 0, 0, 0);
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        for (int k = 0; k < 2; k++) {
          ans.m[i][j] = (ll)(ans.m[i][j] + ((ll)m[i][k] * (ll)(snd.m[k][j])) % mod) % mod;
        }
      }
    }
    return ans;
  }
  int getResult() {
    return m[0][1];
  }
};

int lgpow(Matrix m, int n) {
  Matrix ans(1, 1, 1, 1);
  while (n > 0) {
    if (n % 2 > 0) {
      ans = ans * m;
    }
    m = m * m;
    n /= 2;
  }
  return ans.getResult();
}

int main() {
  in >> n;
  Matrix m(1, 1, 1, 0);
  out << lgpow(m, n - 1) << "\n";
  return 0;
}