#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

typedef ll Data;
typedef vector<Data> Array;
typedef vector<Array> Matrix;

Matrix operator*(const Matrix &lhs, const Matrix &rhs) {
	Matrix res(lhs.size(), Array(rhs[0].size(), 0));
	REP(i, lhs.size()) REP(j, rhs[0].size()) REP(k, rhs.size())
	{
		res[i][j] += (lhs[i][k] * rhs[k][j]) % MOD;
		res[i][j] %= MOD;
	}
	return res;
}
Array operator*(const Matrix &lhs, const Array &rhs) {
	Array res(lhs.size());
	REP(i, lhs.size())
	{
		res[i] = inner_product(begin(lhs[i]), end(lhs[i]), begin(rhs), Data(0));
		res[i] %= MOD;
	}
	return res;
}

Matrix pow(Matrix x, ll n)
{
	Matrix res = { {1,0},{1,0} };
	while (n > 0)
	{
		if (n & 1) res = res * x;
		x = x*x;
		n >>= 1;
	}
	return res;
}


ll fib(ll a)
{
	a++;
	Matrix mat = { {1,1},{1,0} };
	Array p = { 1,0 };
	Array q = pow(mat, a) * p;
	return q[0] % MOD;
}

ll calc(ll a, ll b)
{
	return fib(a) * fib(b) % MOD;
}


int main()
{
	cin.sync_with_stdio(false);
	ll k;
	cin >> k;
	if (k == 1)
	{
		puts("1");
		return 0;
	}
	ll lb = 0, ub = INT_MAX;
	while (ub - lb > 1)
	{
		ll mid = (lb + ub) / 2;
		if (mid % 2)
		{
			ll tmp = mid / 2 + 1;
			ll cnt = (1 + tmp)*tmp;
			if (cnt >= k) ub = mid;
			else lb = mid;
		}
		else
		{
			ll tmp = mid / 2;
			ll cnt = (1 + tmp)*tmp + tmp + 1;
			if (cnt >= k) ub = mid;
			else lb = mid;
		}
	}
	ll tmp = (lb + 1) / 2;
	ll cnt = (1 + tmp)*tmp;
	if (lb % 2 == 0) cnt += tmp + 1;
	ll p = k - cnt - 1;
	ll a;
	ll len = ub / 2 + 1;
	if ((len + 1) / 2 > p) a = 2 * p;
	else a = (len - p - 1) * 2 + 1;
	cout << calc(ub - a, a) << endl;
	return 0;
}
### Prompt

Please create a solution in CPP to the following problem:

Example

Input

5


Output

5

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

typedef ll Data;
typedef vector<Data> Array;
typedef vector<Array> Matrix;

Matrix operator*(const Matrix &lhs, const Matrix &rhs) {
	Matrix res(lhs.size(), Array(rhs[0].size(), 0));
	REP(i, lhs.size()) REP(j, rhs[0].size()) REP(k, rhs.size())
	{
		res[i][j] += (lhs[i][k] * rhs[k][j]) % MOD;
		res[i][j] %= MOD;
	}
	return res;
}
Array operator*(const Matrix &lhs, const Array &rhs) {
	Array res(lhs.size());
	REP(i, lhs.size())
	{
		res[i] = inner_product(begin(lhs[i]), end(lhs[i]), begin(rhs), Data(0));
		res[i] %= MOD;
	}
	return res;
}

Matrix pow(Matrix x, ll n)
{
	Matrix res = { {1,0},{1,0} };
	while (n > 0)
	{
		if (n & 1) res = res * x;
		x = x*x;
		n >>= 1;
	}
	return res;
}


ll fib(ll a)
{
	a++;
	Matrix mat = { {1,1},{1,0} };
	Array p = { 1,0 };
	Array q = pow(mat, a) * p;
	return q[0] % MOD;
}

ll calc(ll a, ll b)
{
	return fib(a) * fib(b) % MOD;
}


int main()
{
	cin.sync_with_stdio(false);
	ll k;
	cin >> k;
	if (k == 1)
	{
		puts("1");
		return 0;
	}
	ll lb = 0, ub = INT_MAX;
	while (ub - lb > 1)
	{
		ll mid = (lb + ub) / 2;
		if (mid % 2)
		{
			ll tmp = mid / 2 + 1;
			ll cnt = (1 + tmp)*tmp;
			if (cnt >= k) ub = mid;
			else lb = mid;
		}
		else
		{
			ll tmp = mid / 2;
			ll cnt = (1 + tmp)*tmp + tmp + 1;
			if (cnt >= k) ub = mid;
			else lb = mid;
		}
	}
	ll tmp = (lb + 1) / 2;
	ll cnt = (1 + tmp)*tmp;
	if (lb % 2 == 0) cnt += tmp + 1;
	ll p = k - cnt - 1;
	ll a;
	ll len = ub / 2 + 1;
	if ((len + 1) / 2 > p) a = 2 * p;
	else a = (len - p - 1) * 2 + 1;
	cout << calc(ub - a, a) << endl;
	return 0;
}
```