#include <iostream>
#include <vector>
#define int long long
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

namespace matrix {
	typedef vector<int> Array;
	typedef vector<Array> Mat;

	Mat E(int n) {
		Mat m(n, Array(n, 0));
		int i; rep(i, n) m[i][i] = 1;
		return m;
	}

	Mat mulmod(Mat a, Mat b, int mod) {
		int i, j, k;
		int h = a.size(), w = b[0].size(), s = a[0].size();
		Mat c(h, Array(w, 0));
		rep(i, h)rep(j, w) rep(k, s) c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
		return c;
	}
	
	Mat powmod(Mat m, int n, int mod) {
		if (n == 0) return E(m.size());
		if (n & 1) return mulmod(m, powmod(m, n - 1, mod), mod);
		return powmod(mulmod(m, m, mod), n / 2, mod);
	}
	
	Array mulmod(Mat a, Array b, int mod) {
		int i, j;
		int h = a.size(), s = a[0].size();
		Array c(h, 0);
		rep(i, h) rep(j, s) c[i] = (c[i] + a[i][j] * b[j]) % mod;
		return c;
	}
}

int toX(int k) {
	int st = 0, ed = 2000000001, mid; //oooxxx, [st, ed)
	while (ed - st >= 2) {
		mid = (st + ed) / 2;
		if ((mid * mid) / 4 <= k) st = mid;
		else ed = mid;
	}
	return st;
}

//x' + y' = xを満たすマス(y', x')を調べる. 
//マス(y, x)にはfib(x+1)*fib(y+2)が何番目のイカ数かが, 0-indexedで書かれている.
//y'の偶奇で模様をつけると法則があるので、O(1)で殴れる.
int toY(int k, int x) {	
	int n = (x + 1) / 2;
	int s = k - (x * x) / 4;
	if (s < (n + 1) / 2) return 2 * s;
	s -= (n + 1) / 2;
	s = n / 2 - 1 - s;
	return 2 * s + 1;
}

int fib(int n, int mod) {
	matrix::Array x(2); x[0] = 0; x[1] = 1;
	matrix::Mat m(2, matrix::Array(2));
	m[0][0] = 0; m[0][1] = 1;
	m[1][0] = 1; m[1][1] = 1;
	m = matrix::powmod(m, n, mod);
	x = matrix::mulmod(m, x, mod);
	return x[0];
}

int mod = 1000000007;

signed main() {
	int k, x, y;
	cin >> k;
	k--;
	x = toX(k);
	y = toY(k, x);
	x -= y;
	cout << fib(x + 1, mod) * fib(y + 2, mod) % mod << endl;
	return 0;
}

### Prompt

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

Example

Input

5


Output

5

### Response

```cpp
#include <iostream>
#include <vector>
#define int long long
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

namespace matrix {
	typedef vector<int> Array;
	typedef vector<Array> Mat;

	Mat E(int n) {
		Mat m(n, Array(n, 0));
		int i; rep(i, n) m[i][i] = 1;
		return m;
	}

	Mat mulmod(Mat a, Mat b, int mod) {
		int i, j, k;
		int h = a.size(), w = b[0].size(), s = a[0].size();
		Mat c(h, Array(w, 0));
		rep(i, h)rep(j, w) rep(k, s) c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
		return c;
	}
	
	Mat powmod(Mat m, int n, int mod) {
		if (n == 0) return E(m.size());
		if (n & 1) return mulmod(m, powmod(m, n - 1, mod), mod);
		return powmod(mulmod(m, m, mod), n / 2, mod);
	}
	
	Array mulmod(Mat a, Array b, int mod) {
		int i, j;
		int h = a.size(), s = a[0].size();
		Array c(h, 0);
		rep(i, h) rep(j, s) c[i] = (c[i] + a[i][j] * b[j]) % mod;
		return c;
	}
}

int toX(int k) {
	int st = 0, ed = 2000000001, mid; //oooxxx, [st, ed)
	while (ed - st >= 2) {
		mid = (st + ed) / 2;
		if ((mid * mid) / 4 <= k) st = mid;
		else ed = mid;
	}
	return st;
}

//x' + y' = xを満たすマス(y', x')を調べる. 
//マス(y, x)にはfib(x+1)*fib(y+2)が何番目のイカ数かが, 0-indexedで書かれている.
//y'の偶奇で模様をつけると法則があるので、O(1)で殴れる.
int toY(int k, int x) {	
	int n = (x + 1) / 2;
	int s = k - (x * x) / 4;
	if (s < (n + 1) / 2) return 2 * s;
	s -= (n + 1) / 2;
	s = n / 2 - 1 - s;
	return 2 * s + 1;
}

int fib(int n, int mod) {
	matrix::Array x(2); x[0] = 0; x[1] = 1;
	matrix::Mat m(2, matrix::Array(2));
	m[0][0] = 0; m[0][1] = 1;
	m[1][0] = 1; m[1][1] = 1;
	m = matrix::powmod(m, n, mod);
	x = matrix::mulmod(m, x, mod);
	return x[0];
}

int mod = 1000000007;

signed main() {
	int k, x, y;
	cin >> k;
	k--;
	x = toX(k);
	y = toY(k, x);
	x -= y;
	cout << fib(x + 1, mod) * fib(y + 2, mod) % mod << endl;
	return 0;
}

```