#include <iostream>
#include <cstdio>
#include <algorithm>
#define PRIM 666013

using namespace std;

struct mat2x2
{
  long long int a, b, c, d;
  mat2x2 operator*(mat2x2 &second)
  {
    mat2x2 res;
    res.a = (((*this).a * second.a) % PRIM + ((*this).b * second.c) % PRIM) % PRIM;
    res.b = (((*this).a * second.b) % PRIM + ((*this).b * second.d) % PRIM) % PRIM;
    res.c = (((*this).b * second.a) % PRIM + ((*this).d * second.c) % PRIM) % PRIM;
    res.d = (((*this).b * second.b) % PRIM + ((*this).d * second.d) % PRIM) % PRIM;
    return res;
  }
  mat2x2& operator*=(mat2x2 &second)
  {
    *this = (*this) * second;
    return *this;
  }
  mat2x2()
  {
    a = 0;
    b = c = d = 1;
  }
  mat2x2(int _a, int _b, int _c, int _d)
  {
    a = _a;
    b = _b;
    c = _c;
    d = _d;
  }
};

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    int k;
    scanf("%d", &k);
    mat2x2 puteri[100];
    for(int i = 2; i <= 34; ++i)
    {
      puteri[i] = puteri[i - 1] * puteri[i - 1];
    }
    mat2x2 final(1, 0, 0, 1);
    int p = 0;
    k -= 2;
    while(1 << p <= k)
    {
      if((1 << p) & k)
        final *= puteri[p + 1];
      ++p;
    }
    printf("%d", (final.b + final.d) % PRIM);
    return 0;
}