#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<vector<int>> Mat;
Mat mul(Mat a,Mat b){
	Mat c = a;
	for(int i = 0 ; i < a.size() ; i++){
		for(int j = 0 ; j < a.size() ; j++){
			c[i][j] = 0;
			for(int k = 0 ; k < a.size() ; k++){
				c[i][j] += a[i][k] * b[k][j];
				c[i][j] %= 1000000007;
			}
		}
	}
	return c;
}
Mat mpow(Mat a,long long n){
	Mat e = {{1,0},{0,1}};
	if( n == 0 ) return e;
	e = mpow(mul(a,a),n/2);
	if( n & 1 ) e = mul(e,a);
	return e;
}

/*
	fn+1  01 f(n)
	fn+2  11 f(n+1)


*/
long long fib(int n){
	Mat m = {{0,1},{1,1}};
	Mat e = {{1,0},{0,1}};
	e = mpow(m,n);
	return e[0][0] + e[0][1];
	/*if( n <= 1 ) return 1;
	if( dp[n] ) return dp[n];
	return dp[n] = fib(n-1) + fib(n-2);	
	*/
}


long long inf = 4e18;
// [0,r]??£????????±
long long total(long long r){
	r++;
	long long k = r / 2;
	if( (double)k*(k-1) > inf ) return inf;
	long long tot = k*(k-1);
	if(r%2==1)tot += k;
	return tot;
}

long long calc(long long n){
	
	long long l = 0 , r = 1e18;
	while( l != r ){
		long long m = (l+r+1) / 2;
		if( total(m) > n ){
			r = m-1;
		}else{
			l = m;
		}
	}
	long long pos = n - total(l);
	long long row = l + 1;
	long long mid = row / 2;
	long long col;
	if( 2*pos >= mid ){
		col = mid - (2*pos - mid)-1;
	}else{
		col = 2*pos;
	}
	//cout << row << " " << col << endl;

	col++;
	return fib(row-col) * fib(col) % 1000000007;
}
signed main(){
	long long n;
	cin >> n;
	--n;
	cout << calc(n) << endl;

}
### Prompt

Generate a cpp solution to the following problem:

Example

Input

5


Output

5

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<vector<int>> Mat;
Mat mul(Mat a,Mat b){
	Mat c = a;
	for(int i = 0 ; i < a.size() ; i++){
		for(int j = 0 ; j < a.size() ; j++){
			c[i][j] = 0;
			for(int k = 0 ; k < a.size() ; k++){
				c[i][j] += a[i][k] * b[k][j];
				c[i][j] %= 1000000007;
			}
		}
	}
	return c;
}
Mat mpow(Mat a,long long n){
	Mat e = {{1,0},{0,1}};
	if( n == 0 ) return e;
	e = mpow(mul(a,a),n/2);
	if( n & 1 ) e = mul(e,a);
	return e;
}

/*
	fn+1  01 f(n)
	fn+2  11 f(n+1)


*/
long long fib(int n){
	Mat m = {{0,1},{1,1}};
	Mat e = {{1,0},{0,1}};
	e = mpow(m,n);
	return e[0][0] + e[0][1];
	/*if( n <= 1 ) return 1;
	if( dp[n] ) return dp[n];
	return dp[n] = fib(n-1) + fib(n-2);	
	*/
}


long long inf = 4e18;
// [0,r]??£????????±
long long total(long long r){
	r++;
	long long k = r / 2;
	if( (double)k*(k-1) > inf ) return inf;
	long long tot = k*(k-1);
	if(r%2==1)tot += k;
	return tot;
}

long long calc(long long n){
	
	long long l = 0 , r = 1e18;
	while( l != r ){
		long long m = (l+r+1) / 2;
		if( total(m) > n ){
			r = m-1;
		}else{
			l = m;
		}
	}
	long long pos = n - total(l);
	long long row = l + 1;
	long long mid = row / 2;
	long long col;
	if( 2*pos >= mid ){
		col = mid - (2*pos - mid)-1;
	}else{
		col = 2*pos;
	}
	//cout << row << " " << col << endl;

	col++;
	return fib(row-col) * fib(col) % 1000000007;
}
signed main(){
	long long n;
	cin >> n;
	--n;
	cout << calc(n) << endl;

}
```