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

Construct a CPP code solution to the problem outlined:

Example

Input

5


Output

5

### Response

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