#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(long long i=0;i<(long long)(n);i++)
#define N 200000
struct mat {
	long long a, b, c, d;
};

mat bas[70];

mat prod(mat x, mat y) {
	mat re;
	re.a = ((x.a*y.a) + (x.b*y.c)) % MOD;
	re.b = ((x.a*y.b) + (x.b*y.d)) % MOD;
	re.c = ((x.c*y.a) + (x.d*y.c)) % MOD;
	re.d = ((x.c*y.b) + (x.d*y.d)) % MOD;
	return re;
}

void pre(void) {
	bas[0] = { 0,1,1,1 };
	f(i, 69)bas[i + 1] = prod(bas[i], bas[i]);
	return;
}


long long fib(long long k) {
	mat re = { 1,0,0,1 };
	f(i, 70) {
		if (k % 2 == 1)re = prod(re, bas[i]);
		k = k / 2;
		if (k == 0)break;
	}
	return re.d;
}

int main() {
  pre();
	long long n, k, m;
	long long x, y, z;
	long long l, r;
	long long s, ans;
	bool v = true;
	ans = 0;
	scanf("%lld", &n);
	l = 0;
	r = 1000000010;
	while (l + 1 < r) {
		m = (l + r) / 2;
		m--;
		x = m * (m + 1);
		if (n <= x)r = m + 1;
		else l = m + 1;
	}
	k = l;
	x = l * (l - 1);
	y = n - x;//1-2k
	if (y <= k)z= 2 * k;
	else {
		z = (2 * k) + 1;
		y -= k;
	}
	if (y <= (k + 1) / 2)x = 2 * y - 1;
	else x = 2 * (k - y + 1);
	y = z - x;
	x = fib(x);
	y = fib(y);
	ans = (x*y) % MOD;
	printf("%lld\n", ans);

	return 0;
}

### Prompt

Please formulate a cpp solution to the following problem:

Example

Input

5


Output

5

### Response

```cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(long long i=0;i<(long long)(n);i++)
#define N 200000
struct mat {
	long long a, b, c, d;
};

mat bas[70];

mat prod(mat x, mat y) {
	mat re;
	re.a = ((x.a*y.a) + (x.b*y.c)) % MOD;
	re.b = ((x.a*y.b) + (x.b*y.d)) % MOD;
	re.c = ((x.c*y.a) + (x.d*y.c)) % MOD;
	re.d = ((x.c*y.b) + (x.d*y.d)) % MOD;
	return re;
}

void pre(void) {
	bas[0] = { 0,1,1,1 };
	f(i, 69)bas[i + 1] = prod(bas[i], bas[i]);
	return;
}


long long fib(long long k) {
	mat re = { 1,0,0,1 };
	f(i, 70) {
		if (k % 2 == 1)re = prod(re, bas[i]);
		k = k / 2;
		if (k == 0)break;
	}
	return re.d;
}

int main() {
  pre();
	long long n, k, m;
	long long x, y, z;
	long long l, r;
	long long s, ans;
	bool v = true;
	ans = 0;
	scanf("%lld", &n);
	l = 0;
	r = 1000000010;
	while (l + 1 < r) {
		m = (l + r) / 2;
		m--;
		x = m * (m + 1);
		if (n <= x)r = m + 1;
		else l = m + 1;
	}
	k = l;
	x = l * (l - 1);
	y = n - x;//1-2k
	if (y <= k)z= 2 * k;
	else {
		z = (2 * k) + 1;
		y -= k;
	}
	if (y <= (k + 1) / 2)x = 2 * y - 1;
	else x = 2 * (k - y + 1);
	y = z - x;
	x = fib(x);
	y = fib(y);
	ans = (x*y) % MOD;
	printf("%lld\n", ans);

	return 0;
}

```