#include <cstdio>

#define MODULO 666013
#define N 2
#define type long long

class Matrix {
 public:
  Matrix& operator*(const Matrix& m) {
    type result[N][N];
    for (type i = 0; i < N; i++) {
      for (type j = 0; j < N; j++) {
        result[i][j] = 0;
        for (type k = 0; k < N; k++) {
          result[i][j] += storage_[i][k] * m.storage_[k][j];
          result[i][j] %= MODULO;
        }
      }
    }
    for (type i = 0; i < N; i++) {
      for (type j = 0; j < N; j++) {
        storage_[i][j] = result[i][j];
      }
    }
    return *this;
  }

  void set(type storage[N][N]) {
    for (type i = 0; i < N; i++) {
      for (type j = 0; j < N; j++) {
        storage_[i][j] = storage[i][j];
      }
    }
  }

  int get() {
    return storage_[1][0];
  }

 private:
  type storage_[N][N];
};

Matrix iden, base;

Matrix raiseToPower(int n, const Matrix& m) {
  if (n == 0) {
    return iden;
  } else if (n == 1) {
    return m;
  } else {
    Matrix half = raiseToPower(n / 2, m);
    half = half * half;
    if (n % 2 == 1) {
      return half * m;
    }
    return half;
  }
}

int main() {
  freopen("kfib.in", "r", stdin);
  freopen("kfib.out", "w", stdout);
  type storage[N][N];
  storage[0][0] = storage[1][1] = 1;
  storage[0][1] = storage[1][0] = 0;
  iden.set(storage);
  storage[0][0] = 0;
  storage[0][1] = storage[1][0] = storage[1][1] = 1;
  base.set(storage);
  int n;
  scanf("%d", &n);
  Matrix finalMatrix = raiseToPower(n, base);
  printf("%d", finalMatrix.get());
  return 0;
}