#include <bits/stdc++.h>

using namespace std;

bool home = 1;

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 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));
}

void addup(int &a, int b) {
  a = add(a, b);
}

void mulup(int &a, int b) {
  a = mul(a, b);
}

int k;
ll l, r;



class Number {
public:
  int a;
  int b;

  Number(int a, int b) : a(a), b(b) {
  }


  void operator = (Number other) {
    a = other.a;
    b = other.b;
  }
}; /// n = (a + sqrt(5) * b)

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

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

Number operator * (Number x, Number y) {
  int aa, bb;
  aa = add(mul(5, mul(x.b, y.b)), mul(x.a, y.a));
  bb = add(mul(x.a, y.b), mul(x.b, y.a));
  x.a = aa;
  x.b = bb;
  return x;
}

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

Number mulsqrt5(Number x) {
  return {mul(5, x.b), x.a};
}

Number operator / (Number x, int value) {
  x.a = dv(x.a, value);
  x.b = dv(x.b, value);
  return x;
}

Number a(dv(1, 2), dv(1, 2)), b(dv(1, 2), add(0, -dv(1, 2)));

Number binet(ll n) {
  Number sol = (a ^ n) - (b ^ n);
  sol = mulsqrt5(sol);
  sol = sol / 5;
  return sol;
}

signed main() {
  freopen ("kfib.in", "r", stdin);
  freopen ("kfib.out", "w", stdout);
  int n;
  cin >> n;
  cout << binet(n).a;

  return 0;
}