#include <cstdio>
#include <string>
#include <list>

using namespace std;

int n;
const int MOD = 666013;

long res[2][2];
long x[2][2];
long back[2][2];

void setvalues(bool result) {
  for (int i = 0; i < 2; ++i) {
    for (int j = 0 ; j < 2; ++j) {
      if (result) {
        res[i][j] = back[i][j];
      } else {
        x[i][j] = back[i][j];
      }
    }
  }
}

void multiply(long a[2][2], long b[2][2]) {
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      long temp = 0;
      for (int k = 0; k < 2; ++k) {
        temp = ( temp + ( a[i][k] * b[k][j] ) % MOD ) % MOD;
      }
      back[i][j] = temp;
    }
  }
}

void solve() {
  scanf("%d", &n);

  // result identity
  res[0][0] = 1;
  res[0][1] = 0;
  res[1][0] = 0;
  res[1][1] = 1;

  // x to be the constant matrix
  x[0][0] = 0;
  x[0][1] = 1;
  x[1][0] = 1;
  x[1][1] = 1;

  // 10010
  int temp = n - 1;
  while (temp) {
    long back[2][2];
    if (temp % 2 != 0) {
     multiply(res, x);
     setvalues(true);
    }
    multiply(x, x);
    setvalues(false);
    temp /= 2;
  }

  printf("%ld\n", res[1][1]);
}

int main() {
  string s = string(__FILE__);
  s = "kfib.cpp";
  size_t pos = s.find_last_of(".");
  freopen((s.substr(0, pos) + ".in").c_str(), "r", stdin);
  freopen((s.substr(0, pos) + ".out").c_str(), "w", stdout);

  solve();
  return 0;
}