#include <cstdio>

using namespace std;

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

  int K, Mod = 666013;
  scanf("%d", &K);
  if (K == 0) {
    printf("0\n");
    return 0;
  }
  if (K == 1 || K == 2) {
    printf("1\n");
    return 0;
  }

  int f1 = 0, f2 = 1;
  int aux, period, i = 1;
  while (true) { //there's a theorem that the priod is about 4*Mod away
    aux = (f1 + f2) % Mod;
    f1 = f2;
    f2 = aux;
    ++i;
    if (i == K)
      break;
    if (f1 == 0 && f2 == 1) {
      period = i - 1;
      break;
    }
  }

  if (i == K) {
    printf("%d\n", f2);
    return 0;
  }
  K %= period;

  while (--K) {
    aux = (f1 + f2) % Mod;
    f1 = f2;
    f2 = aux;
  }
  
  printf("%d\n" , f2);
  
  return 0;
}