#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

ll mod = 1000000007;


ll s_calc(ll a){
	if(a==1)return 1;
	if(a%2==0){
		return a/2*(a/2+1);
	}else{
		return a/2*(a/2+1)+a/2+1;
	}

}

ll fib(ll a){
	ll v[2][2];
	v[0][0] = 1;
	v[0][1] = 1;
	v[1][0] = 1;
	v[1][1] = 0;
	ll res[2][2];
	res[0][0] = 1;
	res[0][1] = 0;
	res[1][0] = 0;
	res[1][1] = 1;
	
	while(a){
		if(a & 1){
			ll tmp[2][2]={};
			rep(i,2){
				rep(j,2){
					rep(k,2){
						tmp[i][j] = (tmp[i][j]+res[i][k]*v[k][j])%mod;
					}
				}
			}
			rep(i,2){
				rep(j,2){
					res[i][j] = tmp[i][j];
				}
			}
		}
		ll tmp[2][2]={};
		rep(i,2){
			rep(j,2){
				rep(k,2){
					tmp[i][j] = (tmp[i][j]+v[i][k]*v[k][j])%mod;
				}
			}
		}
		rep(i,2){
			rep(j,2){
				v[i][j] = tmp[i][j];
			}
		}
		a >>= 1;
	}
	return res[0][0]%mod;
}

int main(){
	ll k;	
	cin >> k;
	ll lb = 0,ub=(ll)2000000000;
	while(ub-lb!=1){
		ll mid = (ub+lb)/2;
		if(s_calc(mid)>=k){
			ub = mid;
		}else{
			lb = mid;
		}
	}
	k -= s_calc(ub-1);
	ll ans;
	if(ub==1){
		ans = 1;
	}else if(ub%2==0){
		ans = 2*(k-1)+1;
	}else{
		//cout << k << " " << ub/2 << endl;
		if(k>ub/4+1){
			ans = 2*(k-1);
		}else{
			ans = 2*(k-1)+1;
		}
	}
	ll ans2 = ub+1-ans;
	//cout << ans << " " << ans2 << endl;
	cout << (fib(ans)*fib(ans2))%mod << endl;
	return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

Example

Input

5


Output

5

### Response

```cpp
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

ll mod = 1000000007;


ll s_calc(ll a){
	if(a==1)return 1;
	if(a%2==0){
		return a/2*(a/2+1);
	}else{
		return a/2*(a/2+1)+a/2+1;
	}

}

ll fib(ll a){
	ll v[2][2];
	v[0][0] = 1;
	v[0][1] = 1;
	v[1][0] = 1;
	v[1][1] = 0;
	ll res[2][2];
	res[0][0] = 1;
	res[0][1] = 0;
	res[1][0] = 0;
	res[1][1] = 1;
	
	while(a){
		if(a & 1){
			ll tmp[2][2]={};
			rep(i,2){
				rep(j,2){
					rep(k,2){
						tmp[i][j] = (tmp[i][j]+res[i][k]*v[k][j])%mod;
					}
				}
			}
			rep(i,2){
				rep(j,2){
					res[i][j] = tmp[i][j];
				}
			}
		}
		ll tmp[2][2]={};
		rep(i,2){
			rep(j,2){
				rep(k,2){
					tmp[i][j] = (tmp[i][j]+v[i][k]*v[k][j])%mod;
				}
			}
		}
		rep(i,2){
			rep(j,2){
				v[i][j] = tmp[i][j];
			}
		}
		a >>= 1;
	}
	return res[0][0]%mod;
}

int main(){
	ll k;	
	cin >> k;
	ll lb = 0,ub=(ll)2000000000;
	while(ub-lb!=1){
		ll mid = (ub+lb)/2;
		if(s_calc(mid)>=k){
			ub = mid;
		}else{
			lb = mid;
		}
	}
	k -= s_calc(ub-1);
	ll ans;
	if(ub==1){
		ans = 1;
	}else if(ub%2==0){
		ans = 2*(k-1)+1;
	}else{
		//cout << k << " " << ub/2 << endl;
		if(k>ub/4+1){
			ans = 2*(k-1);
		}else{
			ans = 2*(k-1)+1;
		}
	}
	ll ans2 = ub+1-ans;
	//cout << ans << " " << ans2 << endl;
	cout << (fib(ans)*fib(ans2))%mod << endl;
	return 0;
}

```