#include <bits/stdc++.h>
using namespace std;

template <class T, class F = multiplies<T>>
T power(T a, long long n, F op = multiplies<T>(), T e = {1}) {
  assert(n >= 0);
  while (n) {
    if (n & 1) e = op(e, a);
    if (n >>= 1) a = op(a, a);
  }
  return e;
}

template <unsigned M> struct modular {
  using m = modular;
  unsigned v;
  modular(long long a = 0) : v((a %= M) < 0 ? a + M : a) {}
  m operator-() const { return m() -= *this; }
  m& operator+=(m r) { if ((v += r.v) >= M) v -= M; return *this; }
  m& operator-=(m r) { if (v < r.v) v += M; v -= r.v; return *this; }
  m& operator*=(m r) { v = (uint64_t)v * r.v % M; return *this; }
  m& operator/=(m r) { return *this *= power(r, M - 2); }
  friend m operator+(m l, m r) { return l += r; }
  friend m operator-(m l, m r) { return l -= r; }
  friend m operator*(m l, m r) { return l *= r; }
  friend m operator/(m l, m r) { return l /= r; }
  friend bool operator==(m l, m r) { return l.v == r.v; }
};

constexpr long long mod = 1e9 + 7;
using mint = modular<mod>;

using mat = array<array<mint, 2>, 2>;
mat operator*(mat l, mat r) {
  mat res;
  for (int i : {0, 1}) {
    for (int k : {0, 1}) {
      for (int j : {0, 1}) {
        res[i][j] += l[i][k] * r[k][j];
      }
    }
  }
  return res;
}
mint fib(long long n) {
  mat a{1, 1, 1, 0}, e{1, 0, 0, 1};
  return power(a, n + 1, multiplies<mat>(), e)[0][0];
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  long long k;
  cin >> k;
  --k;
  long long ok = 0, ng = 2e9;
  while (ng - ok > 1) {
    long long mid = (ok + ng) / 2;
    (mid * (mid + 1) <= k ? ok : ng) = mid;
  }
  k -= ok * (ok + 1);
  long long i = 2 * ok + (k >= ok + 1);
  k %= ok + 1;
  long long j = -1;
  if (k <= ok / 2) {
    j = 2 * k;
  } else {
    k -= ok / 2 + 1;
    long long t = (ok + 1) / 2;
    j = 2 * (t - k - 1) + 1;
  }
  i -= j;
  mint res = fib(i) * fib(j);
  cout << res.v << '\n';
}


### Prompt

Please formulate a CPP solution to the following problem:

Example

Input

5


Output

5

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

template <class T, class F = multiplies<T>>
T power(T a, long long n, F op = multiplies<T>(), T e = {1}) {
  assert(n >= 0);
  while (n) {
    if (n & 1) e = op(e, a);
    if (n >>= 1) a = op(a, a);
  }
  return e;
}

template <unsigned M> struct modular {
  using m = modular;
  unsigned v;
  modular(long long a = 0) : v((a %= M) < 0 ? a + M : a) {}
  m operator-() const { return m() -= *this; }
  m& operator+=(m r) { if ((v += r.v) >= M) v -= M; return *this; }
  m& operator-=(m r) { if (v < r.v) v += M; v -= r.v; return *this; }
  m& operator*=(m r) { v = (uint64_t)v * r.v % M; return *this; }
  m& operator/=(m r) { return *this *= power(r, M - 2); }
  friend m operator+(m l, m r) { return l += r; }
  friend m operator-(m l, m r) { return l -= r; }
  friend m operator*(m l, m r) { return l *= r; }
  friend m operator/(m l, m r) { return l /= r; }
  friend bool operator==(m l, m r) { return l.v == r.v; }
};

constexpr long long mod = 1e9 + 7;
using mint = modular<mod>;

using mat = array<array<mint, 2>, 2>;
mat operator*(mat l, mat r) {
  mat res;
  for (int i : {0, 1}) {
    for (int k : {0, 1}) {
      for (int j : {0, 1}) {
        res[i][j] += l[i][k] * r[k][j];
      }
    }
  }
  return res;
}
mint fib(long long n) {
  mat a{1, 1, 1, 0}, e{1, 0, 0, 1};
  return power(a, n + 1, multiplies<mat>(), e)[0][0];
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  long long k;
  cin >> k;
  --k;
  long long ok = 0, ng = 2e9;
  while (ng - ok > 1) {
    long long mid = (ok + ng) / 2;
    (mid * (mid + 1) <= k ? ok : ng) = mid;
  }
  k -= ok * (ok + 1);
  long long i = 2 * ok + (k >= ok + 1);
  k %= ok + 1;
  long long j = -1;
  if (k <= ok / 2) {
    j = 2 * k;
  } else {
    k -= ok / 2 + 1;
    long long t = (ok + 1) / 2;
    j = 2 * (t - k - 1) + 1;
  }
  i -= j;
  mint res = fib(i) * fib(j);
  cout << res.v << '\n';
}


```