#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const ll M = 1000000007;

struct mat{
	ll a[2][2];
};

mat times(mat x,mat y){
	mat ret;
	rep(i,2)rep(j,2)ret.a[i][j] = x.a[i][0]*y.a[0][j] + x.a[i][1]*y.a[1][j];
	rep(i,2)rep(j,2)ret.a[i][j] %= M;
	return ret;
}

mat I;
void init(){
	rep(i,2)rep(j,2)I.a[i][j] = (i==j)?1:0;
}
mat power(mat x,ll k){
	if(k == 0)return I;
	mat ret = power(x,k/2);
	ret = times(ret,ret);
	if(k%2 == 1)ret = times(ret,x);
	return ret;
}

ll f(ll k){
	mat A;
	rep(i,2)rep(j,2)A.a[i][j] = 1;
	A.a[0][0] = 0;
	return power(A,k+1).a[1][0];
}

ll g(ll n){
	if(n%2 == 0)return n*n/4;
	else return (n*n-1)/4;
}

int main(){
	init();
	ll k;
	cin >> k;
	ll l = 1 , r = 2*M;
	while(l < r){
		ll m = (l+r+1)/2;
		if(g(m) < k)l = m;
		else r = m-1;
	}
	
	ll s = k-g(l);
	s = 2*s-1;
	ll x = (l+1)/2;
	if(s > x)s = 2*x+1-s;
	cout << (f(s)*f(l+1-s))%M << endl;
}
	
### Prompt

Generate a CPP solution to the following problem:

Example

Input

5


Output

5

### Response

```cpp
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const ll M = 1000000007;

struct mat{
	ll a[2][2];
};

mat times(mat x,mat y){
	mat ret;
	rep(i,2)rep(j,2)ret.a[i][j] = x.a[i][0]*y.a[0][j] + x.a[i][1]*y.a[1][j];
	rep(i,2)rep(j,2)ret.a[i][j] %= M;
	return ret;
}

mat I;
void init(){
	rep(i,2)rep(j,2)I.a[i][j] = (i==j)?1:0;
}
mat power(mat x,ll k){
	if(k == 0)return I;
	mat ret = power(x,k/2);
	ret = times(ret,ret);
	if(k%2 == 1)ret = times(ret,x);
	return ret;
}

ll f(ll k){
	mat A;
	rep(i,2)rep(j,2)A.a[i][j] = 1;
	A.a[0][0] = 0;
	return power(A,k+1).a[1][0];
}

ll g(ll n){
	if(n%2 == 0)return n*n/4;
	else return (n*n-1)/4;
}

int main(){
	init();
	ll k;
	cin >> k;
	ll l = 1 , r = 2*M;
	while(l < r){
		ll m = (l+r+1)/2;
		if(g(m) < k)l = m;
		else r = m-1;
	}
	
	ll s = k-g(l);
	s = 2*s-1;
	ll x = (l+1)/2;
	if(s > x)s = 2*x+1-s;
	cout << (f(s)*f(l+1-s))%M << endl;
}
	
```