#include <algorithm>
#include <climits>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> i_i;
int MOD = 1000000007;

vector<vector<int> > matmul(vector<vector<int> >& a, vector<vector<int> >& b) {
	int n = a.size();
	vector<vector<int> > c(n, vector<int>(n));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int k = 0; k < n; k++)
				c[i][j] = (c[i][j] + (ll)a[i][k] * b[k][j]) % MOD;
	return c;
}

vector<vector<int> > matpow(vector<vector<int> >& a, ll m) {
	int n = a.size();
	vector<vector<int> > b(n, vector<int>(n));
	for (int i = 0; i < n; i++)
		b[i][i] = 1;
	for (; m; m >>= 1) {
		if (m & 1) b = matmul(b, a);
		a = matmul(a, a);
	}
	return b;
}

int fib(int n) {
	vector<vector<int> > a(2, vector<int>(2));
	a[0][0] = 0; a[0][1] = 1;
	a[1][0] = 1; a[1][1] = 1;
	return matpow(a, n + 1)[1][1];
}

int main() {
	ll K; cin >> K; K--;
	ll lb = 0, ub = 1000000000;
	while (ub - lb > 1) {
		ll mid = (lb + ub) / 2;
		if (mid * (mid + 1) <= K) lb = mid;
		else ub = mid;
	}
	K -= lb * (lb + 1);
	int n = lb * 2;
	if (K >= lb + 1) {
		K -= lb + 1;
		n++;
	}
	int i;
	if (K * 2 <= n / 2) i = K * 2;
	else i = K * 2 - 1 + n % 2;
	int j = n - i;
	cout << (ll)fib(i) * fib(j) % MOD << endl;
}
### Prompt

Your challenge is to write a cpp solution to the following problem:

Example

Input

5


Output

5

### Response

```cpp
#include <algorithm>
#include <climits>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> i_i;
int MOD = 1000000007;

vector<vector<int> > matmul(vector<vector<int> >& a, vector<vector<int> >& b) {
	int n = a.size();
	vector<vector<int> > c(n, vector<int>(n));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int k = 0; k < n; k++)
				c[i][j] = (c[i][j] + (ll)a[i][k] * b[k][j]) % MOD;
	return c;
}

vector<vector<int> > matpow(vector<vector<int> >& a, ll m) {
	int n = a.size();
	vector<vector<int> > b(n, vector<int>(n));
	for (int i = 0; i < n; i++)
		b[i][i] = 1;
	for (; m; m >>= 1) {
		if (m & 1) b = matmul(b, a);
		a = matmul(a, a);
	}
	return b;
}

int fib(int n) {
	vector<vector<int> > a(2, vector<int>(2));
	a[0][0] = 0; a[0][1] = 1;
	a[1][0] = 1; a[1][1] = 1;
	return matpow(a, n + 1)[1][1];
}

int main() {
	ll K; cin >> K; K--;
	ll lb = 0, ub = 1000000000;
	while (ub - lb > 1) {
		ll mid = (lb + ub) / 2;
		if (mid * (mid + 1) <= K) lb = mid;
		else ub = mid;
	}
	K -= lb * (lb + 1);
	int n = lb * 2;
	if (K >= lb + 1) {
		K -= lb + 1;
		n++;
	}
	int i;
	if (K * 2 <= n / 2) i = K * 2;
	else i = K * 2 - 1 + n % 2;
	int j = n - i;
	cout << (ll)fib(i) * fib(j) % MOD << endl;
}
```