#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
ll mod=1e9+7;
 
mat mul(mat t,mat u){
  mat v(t.size());
  for(int i=0;i<(int)t.size();i++)
    v[i].resize(t.size());
 
  for(int i=0;i<2;i++){
    for(int j=0;j<2;j++){
      v[i][j]=0;
      for(int k=0;k<2;k++){
        v[i][j]+= t[i][k]*u[k][j];
        v[i][j]%=mod;
      }
    }
  }
  return v;
}
 
ll fib(ll x){
  if(x<=1)return 1;
 
  mat A( 2, vec(2,0));
  mat B( 2, vec(2,0));
  A[0][0]=1;
  A[1][1]=1;
  B[0][0]=1;
  B[0][1]=1;
  B[1][0]=1;
  ll n=x;
  while(n>0){
    if(n%2==1)A=mul(A,B);
    n/=2;
    B=mul(B,B);
  }
 
  return (A[1][0]+A[1][1])%mod;
}
 
ll solve(ll si,ll k){
  ll num=(si+1)/2;
  k--;
  ll d;
  if( num/2+num%2 > k ){
    d=k*2;
  }else{
    ll nk= k - (num/2+num%2);
    if(num%2==0){
      d=num-1-nk*2;
    }else{
      d=num-2-nk*2;
    }
  }
  return fib(si-d)* fib(d+1) % mod;
}
 
 
ll func(ll si){
  ll base=si/2;
  ll res = (1+base)*base/2;
  res*=2;
  if(si%2==1)res+=(si+1)/2;
  return res;
}
 
int main(){
  ll K;
  cin>>K;
  ll left=1,right=2000000000LL,mid;
  while(left<right){
    mid=(left+right)/2;
    if( func(mid) < K ) left=mid+1;
    else right=mid;
  }
  cout<<solve(left, K-func(left-1))<<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;
typedef unsigned long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
ll mod=1e9+7;
 
mat mul(mat t,mat u){
  mat v(t.size());
  for(int i=0;i<(int)t.size();i++)
    v[i].resize(t.size());
 
  for(int i=0;i<2;i++){
    for(int j=0;j<2;j++){
      v[i][j]=0;
      for(int k=0;k<2;k++){
        v[i][j]+= t[i][k]*u[k][j];
        v[i][j]%=mod;
      }
    }
  }
  return v;
}
 
ll fib(ll x){
  if(x<=1)return 1;
 
  mat A( 2, vec(2,0));
  mat B( 2, vec(2,0));
  A[0][0]=1;
  A[1][1]=1;
  B[0][0]=1;
  B[0][1]=1;
  B[1][0]=1;
  ll n=x;
  while(n>0){
    if(n%2==1)A=mul(A,B);
    n/=2;
    B=mul(B,B);
  }
 
  return (A[1][0]+A[1][1])%mod;
}
 
ll solve(ll si,ll k){
  ll num=(si+1)/2;
  k--;
  ll d;
  if( num/2+num%2 > k ){
    d=k*2;
  }else{
    ll nk= k - (num/2+num%2);
    if(num%2==0){
      d=num-1-nk*2;
    }else{
      d=num-2-nk*2;
    }
  }
  return fib(si-d)* fib(d+1) % mod;
}
 
 
ll func(ll si){
  ll base=si/2;
  ll res = (1+base)*base/2;
  res*=2;
  if(si%2==1)res+=(si+1)/2;
  return res;
}
 
int main(){
  ll K;
  cin>>K;
  ll left=1,right=2000000000LL,mid;
  while(left<right){
    mid=(left+right)/2;
    if( func(mid) < K ) left=mid+1;
    else right=mid;
  }
  cout<<solve(left, K-func(left-1))<<endl;
  return 0;
}
```