#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

using vec = vint;
using mat = vector<vec>;

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

mat pow(mat A, int n) {
  mat B(A.size(), vec(A.size()));
  for(int i = 0; i < (int)A.size(); i++) B[i][i] = 1;
  while(n > 0) {
    if(n & 1) B = mul(B, A);
    A = mul(A, A);
    n >>= 1;
  }
  return B;
}

int F(int n) {
  mat A(2, vec(2));
  A[0][0] = 1; A[0][1] = 1;
  A[1][0] = 1; A[1][1] = 0;
  mat b(2, vec(1));
  b[0][0] = 1; b[1][0] = 0;
  b = mul(pow(A, n), b);
  return b[0][0];
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  if(0) {
    reps(i, 2, 20) {
      reps(j, 1, i/2+1) cout << F(j)*F(i-j) << " ";
      cout << endl;
    }
  }

  int K;
  cin >> K;

  int row = -1;
  {
    int lb = 0, ub = 3e9;
    while(lb+1 < ub) {
      int mb = (lb+ub)/2;
      //cout<<(mb/2)*((mb+1)/2)<<endl;
      if((mb/2)*((mb+1)/2) < K) lb = mb;
      else ub = mb;
    }
    //cout << lb << endl;
    K -= (lb/2)*((lb+1)/2);
    row = ub;
  }
  //cout<<K<<endl;
  int col = -1;
  if(K <= (row/2+1)/2) {
    col = 2*(K-1)+1;
  } else {
    K -= (row/2+1)/2;
    //cout<<"!"<<K<<endl;
    col = 2*(row/2/2-(K-1));
    //cout<<col<<endl;
  }
  cout << F(col)*F(row-col)%mod <<endl;

  return 0;
}


### Prompt

Your challenge is to write a CPP solution to the following problem:

Example

Input

5


Output

5

### Response

```cpp
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

using vec = vint;
using mat = vector<vec>;

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

mat pow(mat A, int n) {
  mat B(A.size(), vec(A.size()));
  for(int i = 0; i < (int)A.size(); i++) B[i][i] = 1;
  while(n > 0) {
    if(n & 1) B = mul(B, A);
    A = mul(A, A);
    n >>= 1;
  }
  return B;
}

int F(int n) {
  mat A(2, vec(2));
  A[0][0] = 1; A[0][1] = 1;
  A[1][0] = 1; A[1][1] = 0;
  mat b(2, vec(1));
  b[0][0] = 1; b[1][0] = 0;
  b = mul(pow(A, n), b);
  return b[0][0];
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  if(0) {
    reps(i, 2, 20) {
      reps(j, 1, i/2+1) cout << F(j)*F(i-j) << " ";
      cout << endl;
    }
  }

  int K;
  cin >> K;

  int row = -1;
  {
    int lb = 0, ub = 3e9;
    while(lb+1 < ub) {
      int mb = (lb+ub)/2;
      //cout<<(mb/2)*((mb+1)/2)<<endl;
      if((mb/2)*((mb+1)/2) < K) lb = mb;
      else ub = mb;
    }
    //cout << lb << endl;
    K -= (lb/2)*((lb+1)/2);
    row = ub;
  }
  //cout<<K<<endl;
  int col = -1;
  if(K <= (row/2+1)/2) {
    col = 2*(K-1)+1;
  } else {
    K -= (row/2+1)/2;
    //cout<<"!"<<K<<endl;
    col = 2*(row/2/2-(K-1));
    //cout<<col<<endl;
  }
  cout << F(col)*F(row-col)%mod <<endl;

  return 0;
}


```