#include<bits/stdc++.h>
using namespace std;
long long k,_min,_max,x_y,x,y,fib[2],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){
        fib[0]=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;
        }
 
        fib[0]=dp[x%3];
    }
    if(y<3)
    {
        fib[1]=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;
        }
 
        fib[1]=dp[y%3];
    }
 
    cout<<(fib[0] * fib[1])%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,fib[2],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){
        fib[0]=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;
        }
 
        fib[0]=dp[x%3];
    }
    if(y<3)
    {
        fib[1]=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;
        }
 
        fib[1]=dp[y%3];
    }
 
    cout<<(fib[0] * fib[1])%MOD<<endl;
}
```