#include <cstdio>

#define MOD 666013

long long A[2][2] = {{0, 1}, {1, 1}};
long long fib[2][2] = {{0, 1}, {1, 1}};

void exp_mat() {
  long long aux[2][2];

  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      aux[i][j] = (((A[i][0] * A[j][0]) % MOD) + ((A[i][1] * A[1][j]) % MOD)) % MOD;
    }
  }

  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      A[i][j] = aux[i][j];
    }
  }
}

void mul_mat() {
  long long aux[2][2];
  
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      aux[i][j] = (((fib[i][0] * A[j][0]) % MOD) + ((fib[i][1] * A[1][j]) % MOD)) % MOD;
    }
  }

  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      fib[i][j] = aux[i][j];
    }
  }
}


int main() {
  long long k;

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

  scanf("%lld", &k);

  while (k) {
    if (k & 1) {
      mul_mat();
    }

    exp_mat();
    k >>= 1;
  }

  printf("%lld\n", fib[0][0]);

  fcloseall();

  return 0;
}