#include<cstdio>
#include<utility>

using namespace std;

typedef pair<long long,long long> P;

P get(long long N,long long K){
	long long n=N/2;
	long long k=N/2-1;
	if(K>k) return P(-1,-1);
	if(K<=n/2) return P(K*2,N-K*2);
	else return P(2*k+3-K*2,N-(2*k+3-K*2));
}

const long long mod=1000000007;

struct Mat{
	long long a[2][2];
};

Mat mul(Mat m1,Mat m2){
	Mat res;
	for(int i=0;i<2;i++) for(int j=0;j<2;j++) res.a[i][j]=0;
	for(int i=0;i<2;i++) for(int j=0;j<2;j++){
		for(int k=0;k<2;k++){
			res.a[i][j]=(res.a[i][j]+m1.a[i][k]*m2.a[k][j])%mod;
		}
	}
	return res;
}

Mat ex(Mat a,long long e){
	if(e==0){
		Mat res;
		for(int i=0;i<2;i++) for(int j=0;j<2;j++) res.a[i][j]=0;
		for(int i=0;i<2;i++) res.a[i][i]=1;
		return res;
	}
	Mat tmp=ex(a,e/2);
	Mat res=mul(tmp,tmp);
	if(e%2==1){
		res=mul(res,a);
	}
	return res;
}

long long getF(long long a){
	Mat s;
	s.a[0][0]=1;
	s.a[0][1]=1;
	s.a[1][0]=1;
	s.a[1][1]=0;
	Mat x=ex(s,a);
//	printf("%lld %lld\n",a,x.a[1][0]);
	return x.a[1][0];
}

P get(long long K){
	long long lb=0,ub=1000000000;
	while(ub-lb>1){
		long long mid=(ub+lb)/2;
		long long a=mid*(mid+1);
		if(a<K) lb=mid;
		else ub=mid;
	}
	if((lb+1)*(lb+1)<K){
		long long n=lb*2+5;
		long long k=K-(lb+1)*(lb+1);
		return P(n,k);
	}else{
		long long n=lb*2+4;
		long long k=K-lb*(lb+1);
		return P(n,k);
	}
}

int main(){
	long long K;
	scanf("%lld",&K);
	if(K<=6){
		printf("%lld\n",K);
		return 0;
	}
	P p=get(K);
	P p2=get(p.first,p.second);
	long long tmp1=getF(p2.first);
	long long tmp2=getF(p2.second);
	long long ans=tmp1*tmp2;
	ans%=mod;
	ans+=mod;
	ans%=mod;
	printf("%lld\n",ans);
	return 0;
}
### Prompt

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

Example

Input

5


Output

5

### Response

```cpp
#include<cstdio>
#include<utility>

using namespace std;

typedef pair<long long,long long> P;

P get(long long N,long long K){
	long long n=N/2;
	long long k=N/2-1;
	if(K>k) return P(-1,-1);
	if(K<=n/2) return P(K*2,N-K*2);
	else return P(2*k+3-K*2,N-(2*k+3-K*2));
}

const long long mod=1000000007;

struct Mat{
	long long a[2][2];
};

Mat mul(Mat m1,Mat m2){
	Mat res;
	for(int i=0;i<2;i++) for(int j=0;j<2;j++) res.a[i][j]=0;
	for(int i=0;i<2;i++) for(int j=0;j<2;j++){
		for(int k=0;k<2;k++){
			res.a[i][j]=(res.a[i][j]+m1.a[i][k]*m2.a[k][j])%mod;
		}
	}
	return res;
}

Mat ex(Mat a,long long e){
	if(e==0){
		Mat res;
		for(int i=0;i<2;i++) for(int j=0;j<2;j++) res.a[i][j]=0;
		for(int i=0;i<2;i++) res.a[i][i]=1;
		return res;
	}
	Mat tmp=ex(a,e/2);
	Mat res=mul(tmp,tmp);
	if(e%2==1){
		res=mul(res,a);
	}
	return res;
}

long long getF(long long a){
	Mat s;
	s.a[0][0]=1;
	s.a[0][1]=1;
	s.a[1][0]=1;
	s.a[1][1]=0;
	Mat x=ex(s,a);
//	printf("%lld %lld\n",a,x.a[1][0]);
	return x.a[1][0];
}

P get(long long K){
	long long lb=0,ub=1000000000;
	while(ub-lb>1){
		long long mid=(ub+lb)/2;
		long long a=mid*(mid+1);
		if(a<K) lb=mid;
		else ub=mid;
	}
	if((lb+1)*(lb+1)<K){
		long long n=lb*2+5;
		long long k=K-(lb+1)*(lb+1);
		return P(n,k);
	}else{
		long long n=lb*2+4;
		long long k=K-lb*(lb+1);
		return P(n,k);
	}
}

int main(){
	long long K;
	scanf("%lld",&K);
	if(K<=6){
		printf("%lld\n",K);
		return 0;
	}
	P p=get(K);
	P p2=get(p.first,p.second);
	long long tmp1=getF(p2.first);
	long long tmp2=getF(p2.second);
	long long ans=tmp1*tmp2;
	ans%=mod;
	ans+=mod;
	ans%=mod;
	printf("%lld\n",ans);
	return 0;
}
```