#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 2

ll K;
double d_K;
typedef vector<ll> V;
typedef vector<V> MATRIX;
ll mini_ans[7] = {0,1,2,3,4,5,6};

MATRIX calc(MATRIX left,MATRIX right){

	MATRIX ret(SIZE,V(SIZE));

	for(int i = 0; i < SIZE; i++){
		for(int k = 0; k < SIZE; k++)ret[i][k] = 0;
	}

	for(int row = 0; row < SIZE; row++){
		for(int col = 0; col < SIZE; col++){
			for(int a = 0; a < SIZE; a++){
				ret[row][col] += left[row][a]*right[a][col]%MOD;
			}
		}
	}

	return ret;

}

MATRIX pow(MATRIX MULT,ll count){

	MATRIX ret(SIZE,V(SIZE));

	for(int row = 0; row < SIZE; row++){
		for(int col = 0; col < SIZE; col++){
			if(row == col)ret[row][col] = 1;
			else{
				ret[row][col] = 0;
			}
		}
	}

	while(count > 0){
		if(count%2 == 1)ret = calc(ret,MULT);
		MULT = calc(MULT,MULT);
		count /= 2;
	}

	return ret;
}

ll calc_Fibo(ll index){

	MATRIX A(SIZE,V(SIZE));
	A[0][0] = 1;
	A[0][1] = 1;
	A[1][0] = 1;
	A[1][1] = 0;

	A = pow(A,index+1);

	return A[1][0];
}

bool check(ll mid){

	double d_mid = mid;
	double mult;

	if(mid%2 == 0){

		mult = (d_mid*d_mid+2*d_mid)/4;

	}else{

		mult = (d_mid*d_mid+2*d_mid+1)/4;
	}

	if(fabs(mult-d_K) < EPS){
		return true;
	}else{
		return mult > d_K;
	}
}

int main(){

	scanf("%lld",&K);
	if(K <= 6){
		printf("%lld\n",mini_ans[K]);
		return 0;
	}

	d_K = K;

	ll left = 1,right = BIG_NUM,mid = (left+right)/2;
	ll line_num;

	while(left <= right){
		if(check(mid)){
			line_num = mid;
			right = mid-1;
		}else{
			left = mid+1;
		}
		mid = (left+right)/2;
	}

	ll calc_sum;
	if((line_num-1)%2 == 0){

		calc_sum = ((line_num-1)*(line_num-1)+2*(line_num-1))/4;

	}else{

		calc_sum = ((line_num-1)*(line_num-1)+2*(line_num-1)+1)/4;
	}

	ll rank = K-calc_sum;
	ll up_max,index_1,index_2;

	if(line_num%2 == 0){

		if(line_num%4 == 0){

			up_max = line_num/4;

			if(rank > up_max){
				index_1 = (line_num/2)-(2*(rank-(up_max+1)));
			}else{
				index_1 = 2*rank-1;
			}

		}else{

			up_max = (line_num+2)/4;

			if(rank > up_max){
				index_1 = (line_num/2)-(2*(rank-up_max)-1);
			}else{
				index_1 = 2*rank-1;
			}
		}

	}else{

		if(((line_num-1)/2)%2 == 0){

			up_max = (line_num+3)/4;

			if(rank > up_max){
				index_1 = ((line_num+1)/2)-(2*(rank-up_max)-1);
			}else{
				index_1 = 2*rank-1;
			}

		}else{

			up_max = (line_num+1)/4;

			if(rank > up_max){
				index_1 = ((line_num+1)/2)-(2*(rank-(up_max+1)));
			}else{
				index_1 = 2*rank-1;
			}
		}
	}

	index_2 = line_num+1-index_1;

	printf("%lld\n",(calc_Fibo(index_1)*calc_Fibo(index_2))%MOD);

	return 0;
}


### Prompt

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

Example

Input

5


Output

5

### Response

```cpp
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 2

ll K;
double d_K;
typedef vector<ll> V;
typedef vector<V> MATRIX;
ll mini_ans[7] = {0,1,2,3,4,5,6};

MATRIX calc(MATRIX left,MATRIX right){

	MATRIX ret(SIZE,V(SIZE));

	for(int i = 0; i < SIZE; i++){
		for(int k = 0; k < SIZE; k++)ret[i][k] = 0;
	}

	for(int row = 0; row < SIZE; row++){
		for(int col = 0; col < SIZE; col++){
			for(int a = 0; a < SIZE; a++){
				ret[row][col] += left[row][a]*right[a][col]%MOD;
			}
		}
	}

	return ret;

}

MATRIX pow(MATRIX MULT,ll count){

	MATRIX ret(SIZE,V(SIZE));

	for(int row = 0; row < SIZE; row++){
		for(int col = 0; col < SIZE; col++){
			if(row == col)ret[row][col] = 1;
			else{
				ret[row][col] = 0;
			}
		}
	}

	while(count > 0){
		if(count%2 == 1)ret = calc(ret,MULT);
		MULT = calc(MULT,MULT);
		count /= 2;
	}

	return ret;
}

ll calc_Fibo(ll index){

	MATRIX A(SIZE,V(SIZE));
	A[0][0] = 1;
	A[0][1] = 1;
	A[1][0] = 1;
	A[1][1] = 0;

	A = pow(A,index+1);

	return A[1][0];
}

bool check(ll mid){

	double d_mid = mid;
	double mult;

	if(mid%2 == 0){

		mult = (d_mid*d_mid+2*d_mid)/4;

	}else{

		mult = (d_mid*d_mid+2*d_mid+1)/4;
	}

	if(fabs(mult-d_K) < EPS){
		return true;
	}else{
		return mult > d_K;
	}
}

int main(){

	scanf("%lld",&K);
	if(K <= 6){
		printf("%lld\n",mini_ans[K]);
		return 0;
	}

	d_K = K;

	ll left = 1,right = BIG_NUM,mid = (left+right)/2;
	ll line_num;

	while(left <= right){
		if(check(mid)){
			line_num = mid;
			right = mid-1;
		}else{
			left = mid+1;
		}
		mid = (left+right)/2;
	}

	ll calc_sum;
	if((line_num-1)%2 == 0){

		calc_sum = ((line_num-1)*(line_num-1)+2*(line_num-1))/4;

	}else{

		calc_sum = ((line_num-1)*(line_num-1)+2*(line_num-1)+1)/4;
	}

	ll rank = K-calc_sum;
	ll up_max,index_1,index_2;

	if(line_num%2 == 0){

		if(line_num%4 == 0){

			up_max = line_num/4;

			if(rank > up_max){
				index_1 = (line_num/2)-(2*(rank-(up_max+1)));
			}else{
				index_1 = 2*rank-1;
			}

		}else{

			up_max = (line_num+2)/4;

			if(rank > up_max){
				index_1 = (line_num/2)-(2*(rank-up_max)-1);
			}else{
				index_1 = 2*rank-1;
			}
		}

	}else{

		if(((line_num-1)/2)%2 == 0){

			up_max = (line_num+3)/4;

			if(rank > up_max){
				index_1 = ((line_num+1)/2)-(2*(rank-up_max)-1);
			}else{
				index_1 = 2*rank-1;
			}

		}else{

			up_max = (line_num+1)/4;

			if(rank > up_max){
				index_1 = ((line_num+1)/2)-(2*(rank-(up_max+1)));
			}else{
				index_1 = 2*rank-1;
			}
		}
	}

	index_2 = line_num+1-index_1;

	printf("%lld\n",(calc_Fibo(index_1)*calc_Fibo(index_2))%MOD);

	return 0;
}


```