#include <iostream>

using namespace std;
typedef long long ll;
const ll MOD = 1000000007;

struct Matrix2x2 {
	ll a[2][2];
	Matrix2x2 operator*(const Matrix2x2 &m){
		Matrix2x2 c;
		for(int i = 0; i < 2; ++i){
			for(int j = 0; j < 2; ++j){
				ll sum = 0;
				for(int k = 0; k < 2; ++k){
					sum = (sum + a[i][k] * m.a[k][j]) % MOD;
				}
				c.a[i][j] = sum;
			}
		}
		return c;
	}
};

const Matrix2x2 E = { { { 1, 0 }, { 0, 1 } } };

Matrix2x2 modpow(const Matrix2x2 &m, ll e){
	if(e == 0){ return E; }
	Matrix2x2 p = modpow(m, e / 2);
	p = p * p;
	if(e % 2 == 1){ p = p * m; }
	return p;
}

const Matrix2x2 FIB_MAT = { { { 1, 1 }, { 1, 0 } } };
ll fib(ll n){
	Matrix2x2 m = modpow(FIB_MAT, n);
	return (m.a[0][0] + m.a[0][1]) % MOD;
}

int main(){
	ll K;
	cin >> K;
	--K;
	ll left = 0, right = 3400000000ll;
	while(left < right){
		ll center = (left + right) / 2;
		ll begin = center * (center + 1);
		if(K >= begin){
			left = center + 1;
		}else{
			right = center;
		}
	}
	--left;
	K -= left * (left + 1);
	ll answer = 0;
	if(K <= left){
		ll base = left * 2;
		if(K <= left / 2){
			answer = fib(base - K * 2) * fib(K * 2) % MOD;
		}else{
			answer = fib(base - K * 2 + 1) * fib(K * 2 - 1) % MOD;
		}
	}else{
		ll base = left * 2 + 1;
		K -= (left + 1);
		answer = fib(base - K * 2) * fib(K * 2) % MOD;
	}
	cout << answer << endl;
	return 0;
}
### Prompt

Generate a Cpp solution to the following problem:

Example

Input

5


Output

5

### Response

```cpp
#include <iostream>

using namespace std;
typedef long long ll;
const ll MOD = 1000000007;

struct Matrix2x2 {
	ll a[2][2];
	Matrix2x2 operator*(const Matrix2x2 &m){
		Matrix2x2 c;
		for(int i = 0; i < 2; ++i){
			for(int j = 0; j < 2; ++j){
				ll sum = 0;
				for(int k = 0; k < 2; ++k){
					sum = (sum + a[i][k] * m.a[k][j]) % MOD;
				}
				c.a[i][j] = sum;
			}
		}
		return c;
	}
};

const Matrix2x2 E = { { { 1, 0 }, { 0, 1 } } };

Matrix2x2 modpow(const Matrix2x2 &m, ll e){
	if(e == 0){ return E; }
	Matrix2x2 p = modpow(m, e / 2);
	p = p * p;
	if(e % 2 == 1){ p = p * m; }
	return p;
}

const Matrix2x2 FIB_MAT = { { { 1, 1 }, { 1, 0 } } };
ll fib(ll n){
	Matrix2x2 m = modpow(FIB_MAT, n);
	return (m.a[0][0] + m.a[0][1]) % MOD;
}

int main(){
	ll K;
	cin >> K;
	--K;
	ll left = 0, right = 3400000000ll;
	while(left < right){
		ll center = (left + right) / 2;
		ll begin = center * (center + 1);
		if(K >= begin){
			left = center + 1;
		}else{
			right = center;
		}
	}
	--left;
	K -= left * (left + 1);
	ll answer = 0;
	if(K <= left){
		ll base = left * 2;
		if(K <= left / 2){
			answer = fib(base - K * 2) * fib(K * 2) % MOD;
		}else{
			answer = fib(base - K * 2 + 1) * fib(K * 2 - 1) % MOD;
		}
	}else{
		ll base = left * 2 + 1;
		K -= (left + 1);
		answer = fib(base - K * 2) * fib(K * 2) % MOD;
	}
	cout << answer << endl;
	return 0;
}
```