#include <cstdio>
#include <map>
using namespace std;

map<int, int> cache;

int fibonacci(int x) {
   if (cache.count(x) > 0) {
      return cache[x];
   } else if (x == 0 || x == 1 || x == 2) {
      cache[x] = (x > 0 ? 1 : 0);
      return cache[x];
   } else {
      long long n, k, t1, t2, t3, t4;
      n = x / 2;
      k = x - n;
      t1 = fibonacci(k);
      t2 = fibonacci(n + 1);
      t3 = fibonacci(k - 1);
      t4 = fibonacci(n);
      cache[x] = (t1 * t2 + t3 * t4) % 666013;
      return cache[x];
   }
}

int main() {
   int n;
   freopen("kfib.in", "r", stdin);
   freopen("kfib.out", "w", stdout);
   scanf("%d", &n);
   printf("%d\n", fibonacci(n));
}