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

using ll=__int128;
const ll MOD=1e9+7;


using Mat=vector<vector<ll>>;

Mat cross(const Mat &lhs,const Mat& rhs){
    assert(lhs[0].size()==rhs.size());
    int l=lhs.size();
    int m=lhs[0].size();
    int n=rhs[0].size();
    Mat res(l,vector<ll>(n,0LL));
    for(int i=0;i<l;i++){
        for(int k=0;k<m;k++){
            for(int j=0;j<n;j++){
                res[i][j]+=lhs[i][k]*rhs[k][j];
                res[i][j]%=MOD;
            }
        }
    }
    return res;
}

Mat E(ll sz){
    Mat e(sz,vector<ll>(sz,0));
    for(int i=0;i<sz;i++){
        e[i][i]=1;
    }
    return e;
}
Mat pow(const Mat& A,ll x){
    assert(A.size()==A[0].size());
    Mat cpA=A;
    Mat res=E(cpA.size());
    while(x){
        if(x&1) res=cross(res,cpA);
        cpA=cross(cpA,cpA);
        x>>=1;
    }
    return res;
}
// 1 2 3 5 ... 0-indexed
ll fib(ll x){
    Mat A(2,vector<ll>(2,0));
    A[0][0]=A[0][1]=A[1][0]=1;
    A[1][1]=0;
    Mat mat=pow(A,x);
    Mat vec(2,vector<ll>(1,0));
    vec[0][0]=2;
    vec[1][0]=1;
    Mat res=cross(mat,vec);
    return res[1][0];
}

ll getUnder(ll a){
    ll x=a/2+1;
    ll sum=x*(x+1);
    if(a&1) sum-=x;
    else sum-=2*x;
    return sum;
}
int main(){
    long long kbuf;
    cin>>kbuf;
    ll k=kbuf;
    k--;
    ll lb=0;
    ll ub=1e12;
    while(ub-lb>1){
        ll mid=(ub+lb)/2;
        ll sum=getUnder(mid);
        if(sum<=k){
            lb=mid;
        }
        else{
            ub=mid;
        }
    }        
    k-=getUnder(lb);
    
    ll x=lb/2+1;
    ll p;
    if(k<(x+1)/2){
        p=k*2;
    }
    else{
        ll y=x-k-1;
        p=y*2+1;
    }
    cout<<(long long)((fib(p)*fib(lb-p))%MOD)<<endl;
    return 0;
}

### Prompt

Create a solution in cpp for the following problem:

Example

Input

5


Output

5

### Response

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

using ll=__int128;
const ll MOD=1e9+7;


using Mat=vector<vector<ll>>;

Mat cross(const Mat &lhs,const Mat& rhs){
    assert(lhs[0].size()==rhs.size());
    int l=lhs.size();
    int m=lhs[0].size();
    int n=rhs[0].size();
    Mat res(l,vector<ll>(n,0LL));
    for(int i=0;i<l;i++){
        for(int k=0;k<m;k++){
            for(int j=0;j<n;j++){
                res[i][j]+=lhs[i][k]*rhs[k][j];
                res[i][j]%=MOD;
            }
        }
    }
    return res;
}

Mat E(ll sz){
    Mat e(sz,vector<ll>(sz,0));
    for(int i=0;i<sz;i++){
        e[i][i]=1;
    }
    return e;
}
Mat pow(const Mat& A,ll x){
    assert(A.size()==A[0].size());
    Mat cpA=A;
    Mat res=E(cpA.size());
    while(x){
        if(x&1) res=cross(res,cpA);
        cpA=cross(cpA,cpA);
        x>>=1;
    }
    return res;
}
// 1 2 3 5 ... 0-indexed
ll fib(ll x){
    Mat A(2,vector<ll>(2,0));
    A[0][0]=A[0][1]=A[1][0]=1;
    A[1][1]=0;
    Mat mat=pow(A,x);
    Mat vec(2,vector<ll>(1,0));
    vec[0][0]=2;
    vec[1][0]=1;
    Mat res=cross(mat,vec);
    return res[1][0];
}

ll getUnder(ll a){
    ll x=a/2+1;
    ll sum=x*(x+1);
    if(a&1) sum-=x;
    else sum-=2*x;
    return sum;
}
int main(){
    long long kbuf;
    cin>>kbuf;
    ll k=kbuf;
    k--;
    ll lb=0;
    ll ub=1e12;
    while(ub-lb>1){
        ll mid=(ub+lb)/2;
        ll sum=getUnder(mid);
        if(sum<=k){
            lb=mid;
        }
        else{
            ub=mid;
        }
    }        
    k-=getUnder(lb);
    
    ll x=lb/2+1;
    ll p;
    if(k<(x+1)/2){
        p=k*2;
    }
    else{
        ll y=x-k-1;
        p=y*2+1;
    }
    cout<<(long long)((fib(p)*fib(lb-p))%MOD)<<endl;
    return 0;
}

```