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

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
#define rrep(i, m, n) for(int (i)=(m); (i)<(n);  (i)++)
#define erep(i, m, n) for(int (i)=(m); (i)<=(n); (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define rrev(i, m, n) for(int (i)=(n)-1; (i)>=(m); (i)--)
#define erev(i, m, n) for(int (i)=(n); (i)>=(m); (i)--)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define pb            push_back
#define mp            make_pair
template<class T, class S> inline bool minup(T& m, const S x){ return m>(T)x ? (m=(T)x, true) : false; }
template<class T, class S> inline bool maxup(T& m, const S x){ return m<(T)x ? (m=(T)x, true) : false; }

static const ll     INF = 1000000000LL;
static const ll     MOD = 1000000007LL;
static const double EPS = 1E-10;

typedef ll MT;
typedef vector<MT> Array;
typedef vector<Array> Matrix;

Matrix Identity(int n)
{
  Matrix A(n, Array(n));
  rep(i, n) A[i][i] = (MT)1;
  return A;
}

Matrix Multi(const Matrix &A, const Matrix &B, const MT m = (MT)0)
{
  Matrix C(A.size(), Array(B[0].size(), 0));
  if(!m)  rep(i, A.size()) rep(k, B.size()) rep(j, B[0].size()) C[i][j] = (C[i][j] + A[i][k] * B[k][j]);
  else rep(i, A.size()) rep(k, B.size()) rep(j, B[0].size()) C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % m;
  return C;
}

Matrix modPow(Matrix &A, int n, const MT m = (MT)0)
{
  Matrix B = Identity(A.size());
  while(n > (MT)0){
    if(n & ((MT)1)) B = Multi(B, A, m);
    A = Multi(A, A, m);
    n >>= ((MT)1);
  }
  return B;
}

typedef long long int Number;
typedef vector<Number> Vector;
typedef vector<Vector> Matrix;

Matrix modMulti(Matrix A, Matrix B, Number mod = MOD)
{
  Matrix C(A.size(), Vector(B[0].size()));
  rep(i, A.size()) rep(k, B.size()) rep(j, B[0].size()) C[i][j] = (C[i][j] + A[i][k] * B[k][j] + mod) % mod;    // ?????????????????????????????????
  return C;
}

Matrix modPow(Matrix A, ll n, Number mod = MOD)
{
  Matrix B(A.size(), Vector(A.size()));
  rep(i, A.size()) B[i][i] = 1;
  while(n > 0LL){
    if(n & 1LL) B = modMulti(B, A, mod);
    A = modMulti(A, A, mod);
    n >>= 1;
  }
  return B;
}

class getNthTerm
{
public:
  static Matrix init(Number* a, Number* b, Number c, ll k, ll n, ll m)
  {
    Matrix A(k + 1, Vector(k + 1, 0));
    rep(i, k - 1) A[i + 1][i] = 1;
    A[k][k] = 1;
    rep(i, k) A[0][k - i - 1] = b[i];
    A[0][k] = c;
    return modPow(A, n, m);
  }

  static Number get(Number* a, Number* b, Number c, ll k, ll n, ll m)
  {
    Matrix A = init(a, b, c, k, n, m);
    Number ret = 0;
    rep(i, k) ret = (ret + A[k - 1][i] * a[k - i - 1] + m) % m;    // ?????????????????????????????????
    return ret;
  }
};

ll K;
ll a[] = {1, 1};
ll b[] = {1, 1};

inline Number fib(ll n){ return getNthTerm::get(a, b, 0LL, 2LL, n, MOD); }

int main(int argc, char *argv[])
{
  cin >> K;
  K -= 1LL;
  
  ll l = 0LL;
  ll r = INF;
  while(r - l > 1){
    ll mid = (l + r) / 2;
    if(mid * (mid + 1LL) <= K) l = mid;
    else r = mid;
  }
  ll n = 2LL * l;
  ll m = K - l * (l + 1LL);
  if(m >= l + 1LL){
    m -= l + 1LL;
    n += 1LL;
  }
  
  ll nn = n + 1LL - 2LL * m;
  ll mm = 2LL * (m + 1LL) - 1LL;
  if((nn + 1LL) & 1LL){
    cout << fib(nn) * fib(mm) % MOD << endl;
  }
  else{
    if(nn < mm){
      m = n / 2LL + 1LL - m;
      nn = n + 2LL - 2 * m;
      mm = 2LL * m;
    }
    cout << fib(nn) * fib(mm) % MOD << endl;
  }
  
  return 0;
}
### Prompt

Please formulate a cpp solution to the following problem:

Example

Input

5


Output

5

### Response

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

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
#define rrep(i, m, n) for(int (i)=(m); (i)<(n);  (i)++)
#define erep(i, m, n) for(int (i)=(m); (i)<=(n); (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define rrev(i, m, n) for(int (i)=(n)-1; (i)>=(m); (i)--)
#define erev(i, m, n) for(int (i)=(n); (i)>=(m); (i)--)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define pb            push_back
#define mp            make_pair
template<class T, class S> inline bool minup(T& m, const S x){ return m>(T)x ? (m=(T)x, true) : false; }
template<class T, class S> inline bool maxup(T& m, const S x){ return m<(T)x ? (m=(T)x, true) : false; }

static const ll     INF = 1000000000LL;
static const ll     MOD = 1000000007LL;
static const double EPS = 1E-10;

typedef ll MT;
typedef vector<MT> Array;
typedef vector<Array> Matrix;

Matrix Identity(int n)
{
  Matrix A(n, Array(n));
  rep(i, n) A[i][i] = (MT)1;
  return A;
}

Matrix Multi(const Matrix &A, const Matrix &B, const MT m = (MT)0)
{
  Matrix C(A.size(), Array(B[0].size(), 0));
  if(!m)  rep(i, A.size()) rep(k, B.size()) rep(j, B[0].size()) C[i][j] = (C[i][j] + A[i][k] * B[k][j]);
  else rep(i, A.size()) rep(k, B.size()) rep(j, B[0].size()) C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % m;
  return C;
}

Matrix modPow(Matrix &A, int n, const MT m = (MT)0)
{
  Matrix B = Identity(A.size());
  while(n > (MT)0){
    if(n & ((MT)1)) B = Multi(B, A, m);
    A = Multi(A, A, m);
    n >>= ((MT)1);
  }
  return B;
}

typedef long long int Number;
typedef vector<Number> Vector;
typedef vector<Vector> Matrix;

Matrix modMulti(Matrix A, Matrix B, Number mod = MOD)
{
  Matrix C(A.size(), Vector(B[0].size()));
  rep(i, A.size()) rep(k, B.size()) rep(j, B[0].size()) C[i][j] = (C[i][j] + A[i][k] * B[k][j] + mod) % mod;    // ?????????????????????????????????
  return C;
}

Matrix modPow(Matrix A, ll n, Number mod = MOD)
{
  Matrix B(A.size(), Vector(A.size()));
  rep(i, A.size()) B[i][i] = 1;
  while(n > 0LL){
    if(n & 1LL) B = modMulti(B, A, mod);
    A = modMulti(A, A, mod);
    n >>= 1;
  }
  return B;
}

class getNthTerm
{
public:
  static Matrix init(Number* a, Number* b, Number c, ll k, ll n, ll m)
  {
    Matrix A(k + 1, Vector(k + 1, 0));
    rep(i, k - 1) A[i + 1][i] = 1;
    A[k][k] = 1;
    rep(i, k) A[0][k - i - 1] = b[i];
    A[0][k] = c;
    return modPow(A, n, m);
  }

  static Number get(Number* a, Number* b, Number c, ll k, ll n, ll m)
  {
    Matrix A = init(a, b, c, k, n, m);
    Number ret = 0;
    rep(i, k) ret = (ret + A[k - 1][i] * a[k - i - 1] + m) % m;    // ?????????????????????????????????
    return ret;
  }
};

ll K;
ll a[] = {1, 1};
ll b[] = {1, 1};

inline Number fib(ll n){ return getNthTerm::get(a, b, 0LL, 2LL, n, MOD); }

int main(int argc, char *argv[])
{
  cin >> K;
  K -= 1LL;
  
  ll l = 0LL;
  ll r = INF;
  while(r - l > 1){
    ll mid = (l + r) / 2;
    if(mid * (mid + 1LL) <= K) l = mid;
    else r = mid;
  }
  ll n = 2LL * l;
  ll m = K - l * (l + 1LL);
  if(m >= l + 1LL){
    m -= l + 1LL;
    n += 1LL;
  }
  
  ll nn = n + 1LL - 2LL * m;
  ll mm = 2LL * (m + 1LL) - 1LL;
  if((nn + 1LL) & 1LL){
    cout << fib(nn) * fib(mm) % MOD << endl;
  }
  else{
    if(nn < mm){
      m = n / 2LL + 1LL - m;
      nn = n + 2LL - 2 * m;
      mm = 2LL * m;
    }
    cout << fib(nn) * fib(mm) % MOD << endl;
  }
  
  return 0;
}
```