#include<bits/stdc++.h>
using namespace std;
long long k,I,A,x_y,x[2],fib[2],a,i;double D;
#define MOD 1000000007
int dp[3];
int main(){
    cin>>k;
    a=sqrt(k)/16;
    x_y=(long long)(2*sqrt(k-a-0.01))-1;
    A=(x_y+2)*(x_y+2)/4;
    I=(x_y+1)*(x_y+1)/4+1;
    D=1.0*(A+I)/2;
    if(k<=D){x[1]=(k-I)*2;}
    else{x[1]=(A-k)*2+1;}
    x[0]=x_y-x[1];
    
    for(int h=0;h<2;h++){
    if(x[h]<3){
        fib[h]=x[h]+1;
    }
    else{
        dp[0]=1;
        dp[1]=2;
        dp[2]=3;
 
        for(i=3;i<=x[h];i+=3)
        {
            dp[0]=(dp[1]+dp[2])%MOD;
            dp[1]=(dp[2]+dp[0])%MOD;
            dp[2]=(dp[0]+dp[1])%MOD;
        }
 
        fib[h]=dp[x[h]%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,I,A,x_y,x[2],fib[2],a,i;double D;
#define MOD 1000000007
int dp[3];
int main(){
    cin>>k;
    a=sqrt(k)/16;
    x_y=(long long)(2*sqrt(k-a-0.01))-1;
    A=(x_y+2)*(x_y+2)/4;
    I=(x_y+1)*(x_y+1)/4+1;
    D=1.0*(A+I)/2;
    if(k<=D){x[1]=(k-I)*2;}
    else{x[1]=(A-k)*2+1;}
    x[0]=x_y-x[1];
    
    for(int h=0;h<2;h++){
    if(x[h]<3){
        fib[h]=x[h]+1;
    }
    else{
        dp[0]=1;
        dp[1]=2;
        dp[2]=3;
 
        for(i=3;i<=x[h];i+=3)
        {
            dp[0]=(dp[1]+dp[2])%MOD;
            dp[1]=(dp[2]+dp[0])%MOD;
            dp[2]=(dp[0]+dp[1])%MOD;
        }
 
        fib[h]=dp[x[h]%3];
    }
    }
    cout<<(fib[0]*fib[1])%MOD<<endl;
}
```