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

Please formulate a Cpp solution to the following problem:

Example

Input

5


Output

5

### Response

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