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

typedef vector<ll> vec;
typedef vector<vec> mat;
const ll M = 1000000007;

mat mul(mat &A, mat &B){
	mat C(A.size(),vec(B[0].size()));
	for(ll i=0;i<A.size();i++){
		for(ll k=0;k<B.size();k++){
			for(ll j=0;j<B[0].size();j++){
				C[i][j]=(C[i][j]+A[i][k]*B[k][j])%M;
			}
		}
	}
	return C;
}

mat pow(mat A, ll n){
	mat B(A.size(),vec(A.size()));
	for(ll i=0;i<A.size();i++){
		B[i][i]=1;
	}
	while(n>0){
		if(n&1)B=mul(B,A);
		A=mul(A,A);
		n>>=1;
	}
	return B;
}

ll fib(ll n){
	mat A(2,vec(2));
	A[0][0]=1;A[0][1]=1;
	A[1][0]=1;A[1][1]=0;
	A=pow(A,n);
	return A[1][0];
}

ll cnt(ll x){
	if(x<2)return 0;
	return (1+(x/2)*(x%2)+(x/2)*(x/2-1));
}

void solve(ll K,ll *a,ll*b){
	
	ll ng=10000000000,ok=2;
	while(ng-ok-1){
		ll mid=(ng+ok)/2;
		if(K<cnt(mid))ng=mid;
		else ok=mid;
	}
	ll p = cnt(ok),l=ok/2,d=K-p;
	if(l%2){
		if(d<=l/2){
			*a=ok-2*d;
			*b=2+2*d;
		}
		else{
			*a=ok-l+2*(d-l/2);
			*b=2+l-2*(d-l/2);
		}
	}
	else{
		if(d<l/2){
			*a=ok-2*d;
			*b=2+2*d;
		}
		else{
			*a=ok-l+1+2*(d-l/2);
			*b=2+l-1-2*(d-l/2);
		}
	}
}

int main(){
	
	ll K,a,b;
	cin>>K;
	solve(K,&a,&b);
	cout<<fib(a)*fib(b)%M<<endl;
	
	return 0;
}

### Prompt

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

Example

Input

5


Output

5

### Response

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

typedef vector<ll> vec;
typedef vector<vec> mat;
const ll M = 1000000007;

mat mul(mat &A, mat &B){
	mat C(A.size(),vec(B[0].size()));
	for(ll i=0;i<A.size();i++){
		for(ll k=0;k<B.size();k++){
			for(ll j=0;j<B[0].size();j++){
				C[i][j]=(C[i][j]+A[i][k]*B[k][j])%M;
			}
		}
	}
	return C;
}

mat pow(mat A, ll n){
	mat B(A.size(),vec(A.size()));
	for(ll i=0;i<A.size();i++){
		B[i][i]=1;
	}
	while(n>0){
		if(n&1)B=mul(B,A);
		A=mul(A,A);
		n>>=1;
	}
	return B;
}

ll fib(ll n){
	mat A(2,vec(2));
	A[0][0]=1;A[0][1]=1;
	A[1][0]=1;A[1][1]=0;
	A=pow(A,n);
	return A[1][0];
}

ll cnt(ll x){
	if(x<2)return 0;
	return (1+(x/2)*(x%2)+(x/2)*(x/2-1));
}

void solve(ll K,ll *a,ll*b){
	
	ll ng=10000000000,ok=2;
	while(ng-ok-1){
		ll mid=(ng+ok)/2;
		if(K<cnt(mid))ng=mid;
		else ok=mid;
	}
	ll p = cnt(ok),l=ok/2,d=K-p;
	if(l%2){
		if(d<=l/2){
			*a=ok-2*d;
			*b=2+2*d;
		}
		else{
			*a=ok-l+2*(d-l/2);
			*b=2+l-2*(d-l/2);
		}
	}
	else{
		if(d<l/2){
			*a=ok-2*d;
			*b=2+2*d;
		}
		else{
			*a=ok-l+1+2*(d-l/2);
			*b=2+l-1-2*(d-l/2);
		}
	}
}

int main(){
	
	ll K,a,b;
	cin>>K;
	solve(K,&a,&b);
	cout<<fib(a)*fib(b)%M<<endl;
	
	return 0;
}

```