#include <cstring>
#include <stdio.h>

#define MOD 666013

#define LIN 2
#define COL 2

typedef long long ll;

struct Mat {
  int mat[LIN * COL];
  int lin = LIN;
  int col = COL;

  int *operator[](int idx) const { return ((int *)mat) + col * idx; }

  Mat() { memset(mat, 0, sizeof(mat)); }

  Mat(int *v, int l = LIN, int c = COL) {
    memcpy(this->mat, v, sizeof(int) * l * c);
    this->lin = l;
    this->col = c;
  }

  void operator=(const Mat &other) {
    memcpy(this->mat, other.mat, sizeof(int) * LIN * COL);
    this->lin = other.lin;
    this->col = other.col;
  }

  friend Mat operator*(const Mat &a, const Mat &b) {
    Mat res;
    res.lin = a.lin;
    res.col = b.col;
    for (int i = 0; i < a.lin; i++) {
      for (int j = 0; j < b.col; j++) {
        for (int k = 0; k < a.col; k++) {
          res[i][j] = (res[i][j] + ((ll)a[i][k] * b[k][j])) % MOD;
        }
      }
    }
    return res;
  }
};

Mat fastexp(Mat b, int e) {
  Mat p = b;
  while (e) {
    if (e % 2)
      p = p * b;
    b = b * b;
    e /= 2;
  }
  return p;
}

int main() {
  freopen("kfib.in", "r", stdin);
  freopen("kfib.out", "w", stdout);

  int n;
  scanf("%d", &n);
  printf(
      "%d\n",
      (fastexp({(int[]){0, 1, 1, 1}}, n) * (Mat){(int[]){0, 1}, 1, 2}).mat[1]);
  return 0;
}