#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const ll MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
ll all(ll n){
  if(n == 1) return 1;
  ll res = 1;
  res += (n / 2) * (n / 2 + 1);
  if(n % 2 == 0){
    res -= n / 2;
  }
  return res;
}
typedef vector<ll> Array;
typedef vector<Array> Matrix;
Matrix mul(const Matrix &a,const Matrix &b){
  Matrix res(a.size(),Array(b[0].size()));
  REP(i,a.size())REP(j,b[0].size())REP(k,a[0].size()){
    res[i][j]=(res[i][j]+a[i][k]*b[k][j])%MOD;
  }
  return res;
}
Matrix pow(const Matrix &a,ll b){
  if(b==0){
    Matrix res(a.size(),Array(a.size()));
    REP(i,a.size())res[i][i]=1;
    return res;
  }
  Matrix res=pow(mul(a,a),b/2);
  if(b&1)res=mul(res,a);
  return res;
}
ll f(ll x){
  if(x == 0) return 1;
  if(x == 1) return 1;
  Matrix m(2, Array(2));
  m[0][0] = 1; m[0][1] = 1;
  m[1][0] = 1; m[1][1] = 0;
  m = pow(m, x);
  return m[0][0];
}

ll solve(ll K){
  if(K == 1) return 1;
  ll lb = 0, ub = 2000000010LL;
  while(ub - lb > 1){
    ll mid = (ub + lb) / 2;
    if(all(mid) < K){
      lb = mid;
    }else{
      ub = mid;
    }
  }
  K -= all(lb);
  ll x = lb + 1;
  //printf("%lldth of %lld\n", K, x);
  for(ll y = 3; y + y <= x; y += 2){
    if(K == 1) return f(y) * f(x - y) % MOD;
    else K--;
  }
  for(ll y = (x/2 % 2 == 0) ? (x/2) : (x/2 - 1); y >= 2; y -= 2){
    if(K == 1) return f(y) * f(x - y) % MOD;
    else K--;
  }
  return f(x);
}

int main(){
  ll K;
  while(cin>>K && K){
    cout<<solve(K)<<endl;
  }
  return 0;
}
### Prompt

Please provide a CPP coded solution to the problem described below:

Example

Input

5


Output

5

### Response

```cpp
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const ll MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
ll all(ll n){
  if(n == 1) return 1;
  ll res = 1;
  res += (n / 2) * (n / 2 + 1);
  if(n % 2 == 0){
    res -= n / 2;
  }
  return res;
}
typedef vector<ll> Array;
typedef vector<Array> Matrix;
Matrix mul(const Matrix &a,const Matrix &b){
  Matrix res(a.size(),Array(b[0].size()));
  REP(i,a.size())REP(j,b[0].size())REP(k,a[0].size()){
    res[i][j]=(res[i][j]+a[i][k]*b[k][j])%MOD;
  }
  return res;
}
Matrix pow(const Matrix &a,ll b){
  if(b==0){
    Matrix res(a.size(),Array(a.size()));
    REP(i,a.size())res[i][i]=1;
    return res;
  }
  Matrix res=pow(mul(a,a),b/2);
  if(b&1)res=mul(res,a);
  return res;
}
ll f(ll x){
  if(x == 0) return 1;
  if(x == 1) return 1;
  Matrix m(2, Array(2));
  m[0][0] = 1; m[0][1] = 1;
  m[1][0] = 1; m[1][1] = 0;
  m = pow(m, x);
  return m[0][0];
}

ll solve(ll K){
  if(K == 1) return 1;
  ll lb = 0, ub = 2000000010LL;
  while(ub - lb > 1){
    ll mid = (ub + lb) / 2;
    if(all(mid) < K){
      lb = mid;
    }else{
      ub = mid;
    }
  }
  K -= all(lb);
  ll x = lb + 1;
  //printf("%lldth of %lld\n", K, x);
  for(ll y = 3; y + y <= x; y += 2){
    if(K == 1) return f(y) * f(x - y) % MOD;
    else K--;
  }
  for(ll y = (x/2 % 2 == 0) ? (x/2) : (x/2 - 1); y >= 2; y -= 2){
    if(K == 1) return f(y) * f(x - y) % MOD;
    else K--;
  }
  return f(x);
}

int main(){
  ll K;
  while(cin>>K && K){
    cout<<solve(K)<<endl;
  }
  return 0;
}
```