#include<stdio.h>
#include<algorithm>
using namespace std;
long long mat[2][2];
long long now[2][2];
long long tmp[2][2];
int mod=1000000007;
long long fib(long long a){
	now[0][0]=now[1][0]=now[0][1]=1;
	now[1][1]=0;
	mat[0][0]=mat[1][1]=1;
	mat[0][1]=mat[1][0]=0;
	while(a){
		if(a%2){
			tmp[0][0]=now[0][0]*mat[0][0]+now[0][1]*mat[1][0];
			tmp[0][1]=now[0][0]*mat[0][1]+now[0][1]*mat[1][1];
			tmp[1][0]=now[1][0]*mat[0][0]+now[1][1]*mat[1][0];
			tmp[1][1]=now[1][0]*mat[0][1]+now[1][1]*mat[1][1];
			mat[0][0]=tmp[0][0]%mod;mat[0][1]=tmp[0][1]%mod;mat[1][0]=tmp[1][0]%mod;mat[1][1]=tmp[1][1]%mod;
		}
		tmp[0][0]=now[0][0]*now[0][0]+now[0][1]*now[1][0];
		tmp[0][1]=now[0][0]*now[0][1]+now[0][1]*now[1][1];
		tmp[1][0]=now[1][0]*now[0][0]+now[1][1]*now[1][0];
		tmp[1][1]=now[1][0]*now[0][1]+now[1][1]*now[1][1];
		now[0][0]=tmp[0][0]%mod;now[0][1]=tmp[0][1]%mod;now[1][0]=tmp[1][0]%mod;now[1][1]=tmp[1][1]%mod;
		a/=2;
	}
	//printf("%lld\n",mat[0][0]);
	return mat[0][0];
}
int main(){
	long long a;
	scanf("%lld",&a);
	long long left=0;
	long long right=2100000000LL;
	while(left+1<right){
		long long M=(left+right)/2;
		long long t=(M-1)/2*((M-1)/2+1);
		if(M%2==0)t+=M/2;
		//printf("%lld %lld\n",M,t);
		if(t>=a){
			right=M;
		}else{
			left=M;
		}
	}
	long long t=(left-1)/2*((left-1)/2+1);
	if(left%2==0)t+=left/2;
	long long v=a-t;
	//printf("%lld %lld\n",left,v);
	if(v<=(right/2+1)/2){
		long long p=v*2-1;
		long long q=right-p;
	//	printf("%lld %lld\n",p,q);
		printf("%d\n",fib(p)*fib(q)%mod);
	}else{
		long long p=(right/2-v+1)*2;
		long long q=right-p;
	//	printf("%lld %lld\n",p,q);
		printf("%d\n",fib(p)*fib(q)%mod);
	}
}
### Prompt

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

Example

Input

5


Output

5

### Response

```cpp
#include<stdio.h>
#include<algorithm>
using namespace std;
long long mat[2][2];
long long now[2][2];
long long tmp[2][2];
int mod=1000000007;
long long fib(long long a){
	now[0][0]=now[1][0]=now[0][1]=1;
	now[1][1]=0;
	mat[0][0]=mat[1][1]=1;
	mat[0][1]=mat[1][0]=0;
	while(a){
		if(a%2){
			tmp[0][0]=now[0][0]*mat[0][0]+now[0][1]*mat[1][0];
			tmp[0][1]=now[0][0]*mat[0][1]+now[0][1]*mat[1][1];
			tmp[1][0]=now[1][0]*mat[0][0]+now[1][1]*mat[1][0];
			tmp[1][1]=now[1][0]*mat[0][1]+now[1][1]*mat[1][1];
			mat[0][0]=tmp[0][0]%mod;mat[0][1]=tmp[0][1]%mod;mat[1][0]=tmp[1][0]%mod;mat[1][1]=tmp[1][1]%mod;
		}
		tmp[0][0]=now[0][0]*now[0][0]+now[0][1]*now[1][0];
		tmp[0][1]=now[0][0]*now[0][1]+now[0][1]*now[1][1];
		tmp[1][0]=now[1][0]*now[0][0]+now[1][1]*now[1][0];
		tmp[1][1]=now[1][0]*now[0][1]+now[1][1]*now[1][1];
		now[0][0]=tmp[0][0]%mod;now[0][1]=tmp[0][1]%mod;now[1][0]=tmp[1][0]%mod;now[1][1]=tmp[1][1]%mod;
		a/=2;
	}
	//printf("%lld\n",mat[0][0]);
	return mat[0][0];
}
int main(){
	long long a;
	scanf("%lld",&a);
	long long left=0;
	long long right=2100000000LL;
	while(left+1<right){
		long long M=(left+right)/2;
		long long t=(M-1)/2*((M-1)/2+1);
		if(M%2==0)t+=M/2;
		//printf("%lld %lld\n",M,t);
		if(t>=a){
			right=M;
		}else{
			left=M;
		}
	}
	long long t=(left-1)/2*((left-1)/2+1);
	if(left%2==0)t+=left/2;
	long long v=a-t;
	//printf("%lld %lld\n",left,v);
	if(v<=(right/2+1)/2){
		long long p=v*2-1;
		long long q=right-p;
	//	printf("%lld %lld\n",p,q);
		printf("%d\n",fib(p)*fib(q)%mod);
	}else{
		long long p=(right/2-v+1)*2;
		long long q=right-p;
	//	printf("%lld %lld\n",p,q);
		printf("%d\n",fib(p)*fib(q)%mod);
	}
}
```