#include <stdio.h>

#define MODULO 666013

void Inmultire1x2Cu2x2(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];
  }
}

void Inmultire2x2(long long matr1[2][2], long long matr2[2][2], long long modulo) {
  long long result[2][2];
  
  result[0][0] = (matr1[0][0] * matr2[0][0] + matr1[0][1] * matr2[1][0]) % modulo;
  result[0][1] = (matr1[0][0] * matr2[0][1] + matr1[0][1] * matr2[1][1]) % modulo;
  result[1][0] = (matr1[1][0] * matr2[0][0] + matr1[1][1] * matr2[1][0]) % modulo;
  result[1][1] = (matr1[1][0] * matr2[0][1] + matr1[1][1] * matr2[1][1]) % modulo;
  
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      matr1[i][j] = result[i][j];
    }
  }
}

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}};
  while (k) {
    if (k % 2 == 1) {
      Inmultire1x2Cu2x2(termeniFibo, Z, MODULO);
    }
    Inmultire2x2(Z,Z, MODULO);
    k = k / 2;
  }
  printf("%lld\n", termeniFibo[0][0]);
  return 0;
}