#include<bits/stdc++.h>
using namespace std;
long long k,_min,_max,x_y,x,y,fibx,fiby,a,i;double mid;
#define MOD 1000000007
int dp[3];
int main(){
	cin>>k;
	a=sqrt(k)/16;
	x_y=(long long)(2*sqrtl(k-a-0.01))-1;
	_max=(x_y+2)*(x_y+2)/4;
	_min=(x_y+1)*(x_y+1)/4+1;
	mid=1.0*(_max+_min)/2;
	if(k<=mid){y=(k-_min)*2;}
	else{y=(_max-k)*2+1;}
	x=x_y-y;
	if(x<3){
		fibx=x+1;
	}
    else{
		dp[0]=1;
		dp[1]=2;
		dp[2]=3;

		for(i=3;i<=x;i+=3)
		{
			dp[0]=(dp[1]+dp[2])%MOD;
			dp[1]=(dp[2]+dp[0])%MOD;
			dp[2]=(dp[0]+dp[1])%MOD;
		}

		fibx=dp[x%3];
    }
	if(y<3)
	{
		fiby=y+1;
	}
    else{
		dp[0]=1;
		dp[1]=2;
		dp[2]=3;

		for(i=3;i<=y;i+=3)
		{
			dp[0]=(dp[1]+dp[2])%MOD;
			dp[1]=(dp[2]+dp[0])%MOD;
			dp[2]=(dp[0]+dp[1])%MOD;
		}

		fiby=dp[y%3];
	}

	cout<<(fibx * fiby)%MOD<<endl;
}
### 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;
long long k,_min,_max,x_y,x,y,fibx,fiby,a,i;double mid;
#define MOD 1000000007
int dp[3];
int main(){
	cin>>k;
	a=sqrt(k)/16;
	x_y=(long long)(2*sqrtl(k-a-0.01))-1;
	_max=(x_y+2)*(x_y+2)/4;
	_min=(x_y+1)*(x_y+1)/4+1;
	mid=1.0*(_max+_min)/2;
	if(k<=mid){y=(k-_min)*2;}
	else{y=(_max-k)*2+1;}
	x=x_y-y;
	if(x<3){
		fibx=x+1;
	}
    else{
		dp[0]=1;
		dp[1]=2;
		dp[2]=3;

		for(i=3;i<=x;i+=3)
		{
			dp[0]=(dp[1]+dp[2])%MOD;
			dp[1]=(dp[2]+dp[0])%MOD;
			dp[2]=(dp[0]+dp[1])%MOD;
		}

		fibx=dp[x%3];
    }
	if(y<3)
	{
		fiby=y+1;
	}
    else{
		dp[0]=1;
		dp[1]=2;
		dp[2]=3;

		for(i=3;i<=y;i+=3)
		{
			dp[0]=(dp[1]+dp[2])%MOD;
			dp[1]=(dp[2]+dp[0])%MOD;
			dp[2]=(dp[0]+dp[1])%MOD;
		}

		fiby=dp[y%3];
	}

	cout<<(fibx * fiby)%MOD<<endl;
}
```