#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define chmax(a,b) (a<b?(a=b,1):0)
#define chmin(a,b) (a>b?(a=b,1):0)
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

typedef vector<ll> vec;
typedef vector<vec> mat;

ostream &operator<<(ostream &os, const vec &a) {
  FOR(it, a) os << setw(6) << *it << " ";
  return os;
}
ostream &operator<<(ostream &os, const mat &a) {
  FOR(it, a) os << *it << endl;
  return os;
}

mat mul(const mat &A, const mat &B, ll mod) {
  mat C(A.size(), vec(B[0].size()));
  REP(i,A.size())
    REP(j,B[0].size())
    REP(k,B.size())
    C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % mod;
  return C;
}

mat pow(mat A, ll n, ll mod) {
  mat B(A.size(), vec(A.size()));
  REP(i,A.size())
    B[i][i] = 1;
  while(n) {
    if (n&1) B = mul(B, A, mod);
    A = mul(A,A,mod);
    n >>= 1;
  }
  return B;
}

const ll mod = 1e9+7;
mat A;
ll fib(ll n) {
  mat res = pow(A,n,mod);
  return res[0][0] + res[0][1];
}

ll sum(ll n) {
  ll res = (n+1)/2 * ((n+1)/2+1);
  if (n&1) res -= (n+1)/2;
  return res;
}

int main() {
  A = mat(2,vec(2,1));
  A[1][1] = 0;
  ll K;
  while(cin>>K) {
    ll low=0,high=1LL<<31;
    while(low+1<high) {
      ll mid = (low+high)/2;
      if (sum(mid) < K) low = mid;
      else high = mid;
    }
    K -= sum(low);
    K--;
    ll a;
    ll num = (low+2)/2;
    ll num2 = (num+1)/2;
    if (K < num2) {
      a = K*2;
    } else {
      ll t = num-1-K;
      a = t*2+1;
    }
    cout << fib(a)*fib(low-a)%mod << endl;
  }
}
### Prompt

Generate a cpp solution to the following problem:

Example

Input

5


Output

5

### Response

```cpp
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define chmax(a,b) (a<b?(a=b,1):0)
#define chmin(a,b) (a>b?(a=b,1):0)
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

typedef vector<ll> vec;
typedef vector<vec> mat;

ostream &operator<<(ostream &os, const vec &a) {
  FOR(it, a) os << setw(6) << *it << " ";
  return os;
}
ostream &operator<<(ostream &os, const mat &a) {
  FOR(it, a) os << *it << endl;
  return os;
}

mat mul(const mat &A, const mat &B, ll mod) {
  mat C(A.size(), vec(B[0].size()));
  REP(i,A.size())
    REP(j,B[0].size())
    REP(k,B.size())
    C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % mod;
  return C;
}

mat pow(mat A, ll n, ll mod) {
  mat B(A.size(), vec(A.size()));
  REP(i,A.size())
    B[i][i] = 1;
  while(n) {
    if (n&1) B = mul(B, A, mod);
    A = mul(A,A,mod);
    n >>= 1;
  }
  return B;
}

const ll mod = 1e9+7;
mat A;
ll fib(ll n) {
  mat res = pow(A,n,mod);
  return res[0][0] + res[0][1];
}

ll sum(ll n) {
  ll res = (n+1)/2 * ((n+1)/2+1);
  if (n&1) res -= (n+1)/2;
  return res;
}

int main() {
  A = mat(2,vec(2,1));
  A[1][1] = 0;
  ll K;
  while(cin>>K) {
    ll low=0,high=1LL<<31;
    while(low+1<high) {
      ll mid = (low+high)/2;
      if (sum(mid) < K) low = mid;
      else high = mid;
    }
    K -= sum(low);
    K--;
    ll a;
    ll num = (low+2)/2;
    ll num2 = (num+1)/2;
    if (K < num2) {
      a = K*2;
    } else {
      ll t = num-1-K;
      a = t*2+1;
    }
    cout << fib(a)*fib(low-a)%mod << endl;
  }
}
```