#include <stdio.h>

#define MODULO 666013

void inmultire(long long termeniFibo[1][2], long long Z[2][2], long long modulo) {
  long long result[1][2] = {{0, 0}};
  result[0][0] = (termeniFibo[0][0] * Z[0][0] + termeniFibo[0][1] * Z[1][0]) % modulo;
  result[0][1] = (termeniFibo[0][0] * Z[0][1] + termeniFibo[0][1] * Z[1][1]) % modulo;
  for (int i = 0; i < 2; i++) {
    termeniFibo[0][i] = result[0][i];
  }
}

int main() {
  freopen("kfib.in","r",stdin);
  freopen("kfib.out","w",stdout);
  long long k;
  scanf("%lld", &k);
  long long Z[2][2] = {{0, 1}, {1, 1}};
  long long termeniFibo[1][2] = {{0, 1}};
  for (int i = 0; i < k; i++) {
    inmultire(termeniFibo, Z, MODULO);
  }
  printf("%lld", termeniFibo[0][0]);
  return 0;
}