#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef pair<int,int> pint;
typedef pair<long long, long long> pll;

#define MP make_pair
#define PB push_back
#define ALL(s) (s).begin(),(s).end()
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) 
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P) 
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P) 
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) 
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s; }



const long long MOD = 1000000007;

long long mod(long long a, long long m) {
    return (a % m + m) % m;
}
inline long long inverse(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a/b;
        a -= t*b; swap(a, b);
        u -= t*v; swap(u, v);
    }
    return mod(u, m);
}

template<class T> struct Matrix {
    vector<vector<T> > val;
    Matrix(int n = 1, int m = 1) {val.clear(); val.resize(n, vector<T>(m));}
    Matrix(int n, int m, T x) {val.clear(); val.resize(n, vector<T>(m, x));}
    void init(int n, int m, T x = 0) {val.clear(); val.resize(n, vector<T>(m, x));}
    void resize(int n, int m, T x = 0) {val.resize(n); for (int i = 0; i < n; ++i) val[i].resize(m, x);}
    int size() {return val.size();}
    inline vector<T>& operator [] (int i) {return val[i];}
    friend ostream& operator << (ostream& s, Matrix<T> M) {s << endl; 
        for (int i = 0; i < M.val.size(); ++i) s << M[i] << endl; return s;}
};

template<class T> Matrix<T> operator * (Matrix<T> A, Matrix<T> B) {
    Matrix<T> R(A.size(), B[0].size());
    for (int i = 0; i < A.size(); ++i) 
        for (int j = 0; j < B[0].size(); ++j)
            for (int k = 0; k < B.size(); ++k) 
                R[i][j] = mod(R[i][j] + A[i][k] * B[k][j], MOD); 
    return R;
}

template<class T> Matrix<T> pow(Matrix<T> A, long long n) {
    Matrix<T> R(A.size(), A.size());
    for (int i = 0; i < A.size(); ++i) R[i][i] = 1;
    while (n > 0) {
        if (n & 1) R = R * A;
        A = A * A;
        n >>= 1;
    }
    return R;
}

long long num(long long n) {
	if (n & 1) return (n/2 + 1) * (n/2 + 1);
	else return (n/2) * (n/2 + 1);
}


long long K;

int main() {
	Matrix<long long> A(2, 2);
	A[0][0] = 1; A[0][1] = 1; 
	A[1][0] = 1; A[1][1] = 0;
	
	while (cin >> K) { 
		long long lo = 0, hi = 2100000000LL;
		//COUT(hi*hi);
		while (hi - lo > 1) {
			long long med = (lo + hi) / 2;
			//cout << pll(lo, hi) << ", " << med << ": " << num(med) << endl;
			if (num(med) >= K) hi = med;
			else lo = med;
		}
		long long r = K - num(hi-1);
		long long n = hi;
		long long p = r*2-1;
		if ( (n & 1) && r > ((n+1)/2 + 1)/2 ) --p;
		long long q = n + 1 - p;

		long long a1 = pow(A, p)[0][0];
		long long a2 = pow(A, q)[0][0];

		//cout << endl; COUT(K); COUT(pll(n,r)); COUT(p); COUT(q);

		cout << mod(a1 * a2, MOD) << endl;
	}
    return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

Example

Input

5


Output

5

### Response

```cpp
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef pair<int,int> pint;
typedef pair<long long, long long> pll;

#define MP make_pair
#define PB push_back
#define ALL(s) (s).begin(),(s).end()
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) 
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P) 
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P) 
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) 
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s; }



const long long MOD = 1000000007;

long long mod(long long a, long long m) {
    return (a % m + m) % m;
}
inline long long inverse(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a/b;
        a -= t*b; swap(a, b);
        u -= t*v; swap(u, v);
    }
    return mod(u, m);
}

template<class T> struct Matrix {
    vector<vector<T> > val;
    Matrix(int n = 1, int m = 1) {val.clear(); val.resize(n, vector<T>(m));}
    Matrix(int n, int m, T x) {val.clear(); val.resize(n, vector<T>(m, x));}
    void init(int n, int m, T x = 0) {val.clear(); val.resize(n, vector<T>(m, x));}
    void resize(int n, int m, T x = 0) {val.resize(n); for (int i = 0; i < n; ++i) val[i].resize(m, x);}
    int size() {return val.size();}
    inline vector<T>& operator [] (int i) {return val[i];}
    friend ostream& operator << (ostream& s, Matrix<T> M) {s << endl; 
        for (int i = 0; i < M.val.size(); ++i) s << M[i] << endl; return s;}
};

template<class T> Matrix<T> operator * (Matrix<T> A, Matrix<T> B) {
    Matrix<T> R(A.size(), B[0].size());
    for (int i = 0; i < A.size(); ++i) 
        for (int j = 0; j < B[0].size(); ++j)
            for (int k = 0; k < B.size(); ++k) 
                R[i][j] = mod(R[i][j] + A[i][k] * B[k][j], MOD); 
    return R;
}

template<class T> Matrix<T> pow(Matrix<T> A, long long n) {
    Matrix<T> R(A.size(), A.size());
    for (int i = 0; i < A.size(); ++i) R[i][i] = 1;
    while (n > 0) {
        if (n & 1) R = R * A;
        A = A * A;
        n >>= 1;
    }
    return R;
}

long long num(long long n) {
	if (n & 1) return (n/2 + 1) * (n/2 + 1);
	else return (n/2) * (n/2 + 1);
}


long long K;

int main() {
	Matrix<long long> A(2, 2);
	A[0][0] = 1; A[0][1] = 1; 
	A[1][0] = 1; A[1][1] = 0;
	
	while (cin >> K) { 
		long long lo = 0, hi = 2100000000LL;
		//COUT(hi*hi);
		while (hi - lo > 1) {
			long long med = (lo + hi) / 2;
			//cout << pll(lo, hi) << ", " << med << ": " << num(med) << endl;
			if (num(med) >= K) hi = med;
			else lo = med;
		}
		long long r = K - num(hi-1);
		long long n = hi;
		long long p = r*2-1;
		if ( (n & 1) && r > ((n+1)/2 + 1)/2 ) --p;
		long long q = n + 1 - p;

		long long a1 = pow(A, p)[0][0];
		long long a2 = pow(A, q)[0][0];

		//cout << endl; COUT(K); COUT(pll(n,r)); COUT(p); COUT(q);

		cout << mod(a1 * a2, MOD) << endl;
	}
    return 0;
}

```