#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(c) c.begin(),c.end()
#define show(x) cout << #x << " " << x << endl;
typedef long long ll;
ll mod=1e9+7;
vector<ll> ika;
typedef vector<ll> vl;
typedef vector<vl> vv;
vv pro(vv a, vv b){
	vv ret(2,vl(2,0));
	rep(i,2) rep(j,2) rep(k,2) ret[i][j]+=a[i][k]*b[k][j];
	rep(i,2) rep(j,2) ret[i][j]%=mod;
	return ret;
}
ll f(ll a){
	a--;
	vv now(2,vl(2,0)),pw(2,vl(2,1));
	now[0][0]=1,now[1][1]=1,pw[1][1]=0;
	for(int i=0;(a>>i)>0;i++){
		if((a>>i)&1) now=pro(now,pw);
		pw=pro(pw,pw);
	}
	return now[0][0];
}
int main(){
	ll k;
	cin >> k;
	ll lb=-1,ub=2*1e9;
	while(ub-lb>1){
		ll m=(ub+lb)/2;
		ll x=(m/2)*(m/2+1);
		if(m%2==0) x+=m/2+1;
		else x+=2*(m/2+1);
		if(x<k) lb=m;
		else ub=m;
	}
	ll x=ub+4,al=(lb/2)*(lb/2+1),kc=k;
//	show(x);
	if(lb%2==0) al+=lb/2+1;
	else al+=(lb/2+1)*2;
//	show(al);
	k-=al;
	k=x/2-k;
	ll a,b;
	if(k<=(x-2)/4) a=2*k+1,b=x-a;
	else{
		k-=(x-2)/4;
		a=x/4*2-k*2+2,b=x-a;
	}
	if(kc==1) a=2,b=2;
	cout << f(a)*f(b)%mod << endl;
}
### Prompt

Construct a CPP code solution to the problem outlined:

Example

Input

5


Output

5

### Response

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(c) c.begin(),c.end()
#define show(x) cout << #x << " " << x << endl;
typedef long long ll;
ll mod=1e9+7;
vector<ll> ika;
typedef vector<ll> vl;
typedef vector<vl> vv;
vv pro(vv a, vv b){
	vv ret(2,vl(2,0));
	rep(i,2) rep(j,2) rep(k,2) ret[i][j]+=a[i][k]*b[k][j];
	rep(i,2) rep(j,2) ret[i][j]%=mod;
	return ret;
}
ll f(ll a){
	a--;
	vv now(2,vl(2,0)),pw(2,vl(2,1));
	now[0][0]=1,now[1][1]=1,pw[1][1]=0;
	for(int i=0;(a>>i)>0;i++){
		if((a>>i)&1) now=pro(now,pw);
		pw=pro(pw,pw);
	}
	return now[0][0];
}
int main(){
	ll k;
	cin >> k;
	ll lb=-1,ub=2*1e9;
	while(ub-lb>1){
		ll m=(ub+lb)/2;
		ll x=(m/2)*(m/2+1);
		if(m%2==0) x+=m/2+1;
		else x+=2*(m/2+1);
		if(x<k) lb=m;
		else ub=m;
	}
	ll x=ub+4,al=(lb/2)*(lb/2+1),kc=k;
//	show(x);
	if(lb%2==0) al+=lb/2+1;
	else al+=(lb/2+1)*2;
//	show(al);
	k-=al;
	k=x/2-k;
	ll a,b;
	if(k<=(x-2)/4) a=2*k+1,b=x-a;
	else{
		k-=(x-2)/4;
		a=x/4*2-k*2+2,b=x-a;
	}
	if(kc==1) a=2,b=2;
	cout << f(a)*f(b)%mod << endl;
}
```