#include <bits/stdc++.h>

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

const ll mod=1000000007;

typedef valarray<ll> vec;
typedef valarray<vec> mat;


mat mul(mat a,mat b){
	mat c(vec(0LL,2),2);
	for(int i=0;i<2;++i)
		for(int k=0;k<2;++k)
			for(int j=0;j<2;++j)
				c[i][j]=(c[i][j]+a[i][k]*b[k][j]%mod)%mod;
	return c;
}

mat power(mat a,ll n){
	mat b(vec(0LL,2),2);
	b[0][0]=b[1][1]=1LL;
	while(n){
		if(n&1) b=mul(b,a);
		a=mul(a,a);
		n>>=1;
	}
	return b;
}

ll fib(ll n){
	mat a(vec(0LL,2),2);
	a[0][0]=1LL,a[0][1]=1LL;
	a[1][0]=1LL,a[1][1]=0LL;
	a=power(a,n);
	return (a[1][0]+a[1][1])%mod;
}

int main(void){
	ll k;
	cin >> k;

	ll l=0,r=10e9;
	while(r-l>1){
		ll m=(l+r)/2;
		if(m*(m+1)<k)
			l=m;
		else
			r=m;
	}
	ll a=2LL*l+1,b=0;
	ll index=k-l*(l+1);

	if(index>r) index-=r,a++;

	if(index<=(r+1)/2){
		b=1+2*(index-1);
		a-=(b-1);
	}else{
		b=2+2*(r-index);
		a-=(b-1);
	}

	cout << fib(a)*fib(b)%mod << endl;
	return 0;
}


/*
  1    2    3    5    8   13   21   34   55   89
  2    4    6   10   16   26   42   68  110  178
  3    6    9   15   24   39   63  102  165  267
  5   10   15   25   40   65  105  170  275  445
  8   16   24   40   64  104  168  272  440  712
 13   26   39   65  104  169  273  442  715 1157
 21   42   63  105  168  273  441  714 1155 1869
 34   68  102  170  272  442  714 1156 1870 3026
 55  110  165  275  440  715 1155 1870 3025 4895
 89  178  267  445  712 1157 1869 3026 4895 7921
 */
### Prompt

Construct a Cpp code solution to the problem outlined:

Example

Input

5


Output

5

### Response

```cpp
#include <bits/stdc++.h>

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

const ll mod=1000000007;

typedef valarray<ll> vec;
typedef valarray<vec> mat;


mat mul(mat a,mat b){
	mat c(vec(0LL,2),2);
	for(int i=0;i<2;++i)
		for(int k=0;k<2;++k)
			for(int j=0;j<2;++j)
				c[i][j]=(c[i][j]+a[i][k]*b[k][j]%mod)%mod;
	return c;
}

mat power(mat a,ll n){
	mat b(vec(0LL,2),2);
	b[0][0]=b[1][1]=1LL;
	while(n){
		if(n&1) b=mul(b,a);
		a=mul(a,a);
		n>>=1;
	}
	return b;
}

ll fib(ll n){
	mat a(vec(0LL,2),2);
	a[0][0]=1LL,a[0][1]=1LL;
	a[1][0]=1LL,a[1][1]=0LL;
	a=power(a,n);
	return (a[1][0]+a[1][1])%mod;
}

int main(void){
	ll k;
	cin >> k;

	ll l=0,r=10e9;
	while(r-l>1){
		ll m=(l+r)/2;
		if(m*(m+1)<k)
			l=m;
		else
			r=m;
	}
	ll a=2LL*l+1,b=0;
	ll index=k-l*(l+1);

	if(index>r) index-=r,a++;

	if(index<=(r+1)/2){
		b=1+2*(index-1);
		a-=(b-1);
	}else{
		b=2+2*(r-index);
		a-=(b-1);
	}

	cout << fib(a)*fib(b)%mod << endl;
	return 0;
}


/*
  1    2    3    5    8   13   21   34   55   89
  2    4    6   10   16   26   42   68  110  178
  3    6    9   15   24   39   63  102  165  267
  5   10   15   25   40   65  105  170  275  445
  8   16   24   40   64  104  168  272  440  712
 13   26   39   65  104  169  273  442  715 1157
 21   42   63  105  168  273  441  714 1155 1869
 34   68  102  170  272  442  714 1156 1870 3026
 55  110  165  275  440  715 1155 1870 3025 4895
 89  178  267  445  712 1157 1869 3026 4895 7921
 */
```