#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007

typedef __int128 ll;
typedef vector< vector<ll> > Matrix;

Matrix operator *(const Matrix& A, const Matrix& B) {
	Matrix ret(2, vector<ll>(2, 0));
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < 2; ++j) {
			for (int k = 0; k < 2; ++k) {
				ret[i][j] = (ret[i][j] + A[i][k] * B[k][j]) % MOD;
			}
		}
	}
	return ret;
}

ll fib(ll n) {
	if (n == 0) return 1;

	Matrix A = {
		{1, 1},
		{1, 0},
	};
	Matrix B = {
		{1, 0},
		{0, 1},
	};
	for (ll i = 1; i <= n; i <<= 1) {
		if (n & i) {
			B = A * B;
		}
		A = A * A;
	}
	return (B[1][0] + B[1][1]) % MOD;
}

int main() {
	long long _K; cin >> _K;
	ll K = _K-1;

	ll l = 0, r = 1000000000000LL;
	while (l < r-1) {
		ll m = (l + r) / 2;
		if ( m * (m + 1) <= K ) {
			l = m;
		}
		else {
			r = m;
		}
	}

	K -= l * (l+1);
	ll pos = l * 2; ++l;
	if (K >= l) {
		K -= l;
		++pos;
	}

	ll x = K >= (l+1)/2 ? l - (K*2-(l+1)) - 2 : K*2;
//	cout << (long long)K << " " << (long long)l << " " << (long long)pos << " " << (long long)x << endl;
	cout << ((long long)(fib(pos-x+1) * fib(x+1))%MOD) << endl;
/*
	vector<ll> v;
	for (int i = 1; i < 10; ++i) {
		for (int j = 1; j < 10; ++j) {
			int v = (int)(fib(i) * fib(j));
			if (i <= j) {
				printf("%4d ", v);
			}
			else {
				printf("     ");
			}
//			v.push_back(fib(i) * fib(j));
		}
		cout << endl;
	}
*/
//	sort(v.begin(), v.end());
//	v.erase(unique(v.begin(), v.end()), v.end());
}
### Prompt

Please provide a cpp coded solution to the problem described below:

Example

Input

5


Output

5

### Response

```cpp
#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007

typedef __int128 ll;
typedef vector< vector<ll> > Matrix;

Matrix operator *(const Matrix& A, const Matrix& B) {
	Matrix ret(2, vector<ll>(2, 0));
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < 2; ++j) {
			for (int k = 0; k < 2; ++k) {
				ret[i][j] = (ret[i][j] + A[i][k] * B[k][j]) % MOD;
			}
		}
	}
	return ret;
}

ll fib(ll n) {
	if (n == 0) return 1;

	Matrix A = {
		{1, 1},
		{1, 0},
	};
	Matrix B = {
		{1, 0},
		{0, 1},
	};
	for (ll i = 1; i <= n; i <<= 1) {
		if (n & i) {
			B = A * B;
		}
		A = A * A;
	}
	return (B[1][0] + B[1][1]) % MOD;
}

int main() {
	long long _K; cin >> _K;
	ll K = _K-1;

	ll l = 0, r = 1000000000000LL;
	while (l < r-1) {
		ll m = (l + r) / 2;
		if ( m * (m + 1) <= K ) {
			l = m;
		}
		else {
			r = m;
		}
	}

	K -= l * (l+1);
	ll pos = l * 2; ++l;
	if (K >= l) {
		K -= l;
		++pos;
	}

	ll x = K >= (l+1)/2 ? l - (K*2-(l+1)) - 2 : K*2;
//	cout << (long long)K << " " << (long long)l << " " << (long long)pos << " " << (long long)x << endl;
	cout << ((long long)(fib(pos-x+1) * fib(x+1))%MOD) << endl;
/*
	vector<ll> v;
	for (int i = 1; i < 10; ++i) {
		for (int j = 1; j < 10; ++j) {
			int v = (int)(fib(i) * fib(j));
			if (i <= j) {
				printf("%4d ", v);
			}
			else {
				printf("     ");
			}
//			v.push_back(fib(i) * fib(j));
		}
		cout << endl;
	}
*/
//	sort(v.begin(), v.end());
//	v.erase(unique(v.begin(), v.end()), v.end());
}
```