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


#define int long long


#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;

typedef vector<vint>mat;

mat mul(mat A,mat B){
    mat C(A.size(),vint(B[0].size()));

    for(int i=0;i<A.size();i++){
        for(int j=0;j<B[0].size();j++){
            for(int k=0;k<A[0].size();k++){
                C[i][j]=(C[i][j]+A[i][k]*B[k][j])%mod;
            }
        }
    }

    return C;
}

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

int F(int n){
    mat A(2,vint(2));
    A[0][0]=1;A[0][1]=1;
    A[1][0]=1;A[1][1]=0;

    mat X(2,vint(1));
    X[0][0]=1;X[1][0]=0;

    X=mul(matpow(A,n),X);
    return X[0][0];
}

signed main(){
    /*
    for(int i=2;i<=20;i++){
        for(int j=1;i-j>=1;j++){
            cout<<F(j)*F(i-j)<<" ";
        }cout<<endl;
    }*/

    int K;
    cin>>K;
    int lb=0,ub=1000000000;
    while(ub-lb>1){
        int mid=(ub+lb)/2;
        if(mid*(mid+1)<K)lb=mid;
        else ub=mid;
    }

    K-=lb*(lb+1);

    int s=ub*2;

    if(K>ub){
        K-=ub;
        s++;
    }


    int t=s/2;
    int w;
    if(K<=(t+1)/2){
        w=K*2-1;
    }
    else{
        K=t-K+1;
        w=K*2;
    }
    cout<<F(w)*F(s-w)%mod<<endl;

    return 0;
}
### Prompt

In CPP, your task is to solve the following problem:

Example

Input

5


Output

5

### Response

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


#define int long long


#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;

typedef vector<vint>mat;

mat mul(mat A,mat B){
    mat C(A.size(),vint(B[0].size()));

    for(int i=0;i<A.size();i++){
        for(int j=0;j<B[0].size();j++){
            for(int k=0;k<A[0].size();k++){
                C[i][j]=(C[i][j]+A[i][k]*B[k][j])%mod;
            }
        }
    }

    return C;
}

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

int F(int n){
    mat A(2,vint(2));
    A[0][0]=1;A[0][1]=1;
    A[1][0]=1;A[1][1]=0;

    mat X(2,vint(1));
    X[0][0]=1;X[1][0]=0;

    X=mul(matpow(A,n),X);
    return X[0][0];
}

signed main(){
    /*
    for(int i=2;i<=20;i++){
        for(int j=1;i-j>=1;j++){
            cout<<F(j)*F(i-j)<<" ";
        }cout<<endl;
    }*/

    int K;
    cin>>K;
    int lb=0,ub=1000000000;
    while(ub-lb>1){
        int mid=(ub+lb)/2;
        if(mid*(mid+1)<K)lb=mid;
        else ub=mid;
    }

    K-=lb*(lb+1);

    int s=ub*2;

    if(K>ub){
        K-=ub;
        s++;
    }


    int t=s/2;
    int w;
    if(K<=(t+1)/2){
        w=K*2-1;
    }
    else{
        K=t-K+1;
        w=K*2;
    }
    cout<<F(w)*F(s-w)%mod<<endl;

    return 0;
}
```