#include <cstdio>
#include <map>

const int MOD = 666013;

std::map<int, int> f;

int fib(int n) {
  int k = n / 2;
  if(f[n] > 0)
    return f[n];
  else if(n % 2 == 0)
    return f[n] = ((long long)fib(k) * fib(k) + (long long)fib(k - 1) * fib(k - 1)) % MOD;
  else
    return f[n] = ((long long)fib(k - 1) * fib(k) + (long long)fib(k) * fib(k + 1)) % MOD;
}

int main() {
  int n;
  f[0] = f[1] = 1;
  FILE *fin = fopen("kfib.in", "r");
  fscanf(fin, "%d", &n);
  fclose(fin);
  FILE *fout = fopen("kfib.out", "w");
  fprintf(fout, "%d", fib(n - 1));
  fclose(fout);
  return 0;
}