#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int M = 666013;

int add(int a, int b) {
  a += b;
  if (a >= M) return a - M;
  if (a < 0) return a + M;
  return a;
}

int mul(int a, int b) {
  return a * (ll) b % M;
}

int mul(int a, int b, int c) {
  return mul(a, mul(b, c));
}

int pw(int a, int b) {
  int r = 1;
  while (b) {
    if (b & 1) r = mul(r, a);
    a = mul(a, a);
    b /= 2;
  }
  return r;
}

int dv(int a, int b) {
  return mul(a, pw(b, M - 2));
}

struct T {
  int a, b;
};

T operator * (T x, T y) {
  return {add(mul(x.a, y.a), mul(5, x.b, y.b)), add(mul(x.a, y.b), mul(x.b, y.a))};
}

T operator + (T x, T y) {
  return {add(x.a, y.a), add(x.b, y.b)};
}

T operator - (T x, T y) {
  return {add(x.a, -y.a), add(x.b, -y.b)};
}

T operator ^ (T a, int b) {
  T sol = {1, 0};
  while (b) {
    if (b & 1) sol = sol * a;
    a = a * a;
    b /= 2;
  }
  return sol;
}

T operator / (T x1, T x2) {
  int a1 = x1.a;
  int b1 = x1.b;
  int a2 = x2.a;
  int b2 = x2.b;
  T dow = T{a2, b2} * T{a2, add(0, -b2)};
  int down = add(mul(a2, a2), add(0, -mul(5, b2, b2)));
  T t1 = {a1, b1};
  T t2 = {a2, add(0, -b2)};
  T t = t1 * t2;
  return {dv(t.a, down), dv(t.b, down)};
}

signed main() {
#ifdef ONPC
  freopen ("input.txt", "r", stdin);
#else
  ios::sync_with_stdio(0); cin.tie(0);
#endif // ONPC

  if (0) {
    T a = {105, 3};
    T b = {2, 1};

    T c = a / b;
    T d = c * b;
    cout << d.a << " " << d.b << "\n";
    exit(0);
  }

  T phi = {1, 1};
  phi = phi / T{2, 0};

  T zero = {0, 0};
  T negphi = zero - phi;

  int n;
  cin >> n;
  T a = phi ^ n;
  T b = negphi ^ n;

  b = T{1, 0} / b;
  a = a - b;

  T sqrt5 = {0, 1};


  T sol = a / sqrt5;
  cout << sol.a << "\n";


  return 0;
}