#include "bits/stdc++.h"

using namespace std;

using ll = long long;

template <typename T>
using matrix = std::vector<std::vector<T>>;

constexpr long long mod = 1e9 + 7;

template <typename T>
matrix<T> modmul(const matrix<T> &l, const matrix<T> &r)
{
    matrix<T> ret(l.size(), std::vector<T>(r[0].size()));
    for (int i = 0; i < (int)l.size(); i++)
    {
        for (int k = 0; k < (int)r.size(); k++)
        {
            for (int j = 0; j < (int)r[0].size(); j++)
            {
                ret[i][j] += l[i][k] * r[k][j] % mod;
                ret[i][j] %= mod;
            }
        }
    }
    return ret;
}

template <typename T>
std::vector<T> modmul(const matrix<T> &a, const std::vector<T> &x)
{
    const int n = a.size();
    const int m = x.size();
    std::vector<T> ret(n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            ret[i] += a[i][j] * x[j] % mod;
            ret[i] %= mod;
        }
    }
    return ret;
}

template <typename T>
matrix<T> eye(const int n)
{
    matrix<T> ret(n, std::vector<T>(n));
    for (int i = 0; i < n; i++)
        ret[i][i] = 1;
    return ret;
}

template <typename T>
matrix<T> modpow(matrix<T> x, long long n)
{
    auto ret = eye<T>(x.size());
    while (n)
    {
        if (n & 1)
            ret = modmul(ret, x);
        x = modmul(x, x);
        n /= 2;
    }
    return ret;
}

long long fib(long long n)
{
    if (n <= 1)
        return 1;
    matrix<ll> mat(2, vector<ll>(2, 1));
    mat[1][1] = 0;
    vector<ll> v(2, 1);
    auto ret = modmul(modpow(mat, n - 1), v);
    return ret[0];
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll k;
    cin >> k;
    vector<ll> v = {0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 13, 15, 16};
    if (k < 10)
    {
        cout << v[k] << endl;
        return 0;
    }
    auto f = [](ll m) {
        return (m % 2 ? (m - 1) / 2 * (m + 1) / 2 + (m + 1) / 2 : m / 2 * (m + 2) / 2);
    };
    // 1,1,2,2,...,n,n,..の何番目か
    ll lb = 1, ub = 3e9;
    while (ub - lb > 1)
    {
        //cout << lb << " " << ub << endl;
        ll m = (lb + ub) / 2;
        if (f(m) >= k)
        {
            ub = m;
        }
        else
        {
            lb = m;
        }
        assert(f(lb) < k && k <= f(ub));
    }
    //cout << lb << " " << ub << endl;
    ll r = k - f(lb);
    // f[ub]の線上, (ub+1)/2個中r個目
    ll cnt = (ub + 1) / 2;
    assert(1 <= r && r <= cnt);
    ll index, i, j;
    if (cnt % 2)
    {
        // 奇数個
        if (r <= (cnt + 1) / 2)
        {
            index = 2 * (r - 1);
        }
        else
        {
            index = cnt - 2 - 2 * (r - (cnt + 1) / 2 - 1);
        }
    }
    else
    {
        // 偶数個
        if (r <= cnt / 2)
        {
            index = 2 * (r - 1);
        }
        else
        {
            index = cnt - 1 - 2 * (r - cnt / 2 - 1);
        }
    }
    i = ub - index;
    j = 1 + index;
    cout << fib(i) * fib(j) % mod << endl;
}


### Prompt

Please create a solution in Cpp to the following problem:

Example

Input

5


Output

5

### Response

```cpp
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

template <typename T>
using matrix = std::vector<std::vector<T>>;

constexpr long long mod = 1e9 + 7;

template <typename T>
matrix<T> modmul(const matrix<T> &l, const matrix<T> &r)
{
    matrix<T> ret(l.size(), std::vector<T>(r[0].size()));
    for (int i = 0; i < (int)l.size(); i++)
    {
        for (int k = 0; k < (int)r.size(); k++)
        {
            for (int j = 0; j < (int)r[0].size(); j++)
            {
                ret[i][j] += l[i][k] * r[k][j] % mod;
                ret[i][j] %= mod;
            }
        }
    }
    return ret;
}

template <typename T>
std::vector<T> modmul(const matrix<T> &a, const std::vector<T> &x)
{
    const int n = a.size();
    const int m = x.size();
    std::vector<T> ret(n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            ret[i] += a[i][j] * x[j] % mod;
            ret[i] %= mod;
        }
    }
    return ret;
}

template <typename T>
matrix<T> eye(const int n)
{
    matrix<T> ret(n, std::vector<T>(n));
    for (int i = 0; i < n; i++)
        ret[i][i] = 1;
    return ret;
}

template <typename T>
matrix<T> modpow(matrix<T> x, long long n)
{
    auto ret = eye<T>(x.size());
    while (n)
    {
        if (n & 1)
            ret = modmul(ret, x);
        x = modmul(x, x);
        n /= 2;
    }
    return ret;
}

long long fib(long long n)
{
    if (n <= 1)
        return 1;
    matrix<ll> mat(2, vector<ll>(2, 1));
    mat[1][1] = 0;
    vector<ll> v(2, 1);
    auto ret = modmul(modpow(mat, n - 1), v);
    return ret[0];
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll k;
    cin >> k;
    vector<ll> v = {0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 13, 15, 16};
    if (k < 10)
    {
        cout << v[k] << endl;
        return 0;
    }
    auto f = [](ll m) {
        return (m % 2 ? (m - 1) / 2 * (m + 1) / 2 + (m + 1) / 2 : m / 2 * (m + 2) / 2);
    };
    // 1,1,2,2,...,n,n,..の何番目か
    ll lb = 1, ub = 3e9;
    while (ub - lb > 1)
    {
        //cout << lb << " " << ub << endl;
        ll m = (lb + ub) / 2;
        if (f(m) >= k)
        {
            ub = m;
        }
        else
        {
            lb = m;
        }
        assert(f(lb) < k && k <= f(ub));
    }
    //cout << lb << " " << ub << endl;
    ll r = k - f(lb);
    // f[ub]の線上, (ub+1)/2個中r個目
    ll cnt = (ub + 1) / 2;
    assert(1 <= r && r <= cnt);
    ll index, i, j;
    if (cnt % 2)
    {
        // 奇数個
        if (r <= (cnt + 1) / 2)
        {
            index = 2 * (r - 1);
        }
        else
        {
            index = cnt - 2 - 2 * (r - (cnt + 1) / 2 - 1);
        }
    }
    else
    {
        // 偶数個
        if (r <= cnt / 2)
        {
            index = 2 * (r - 1);
        }
        else
        {
            index = cnt - 1 - 2 * (r - cnt / 2 - 1);
        }
    }
    i = ub - index;
    j = 1 + index;
    cout << fib(i) * fib(j) % mod << endl;
}


```