#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>

using namespace std;
typedef long long ll;

const ll MD = 1e9+7;

template<ll MD>
struct SMatrix {
    typedef ll D;
    vector<valarray<D>> d;
    int N, M;
    SMatrix(int N, int M) : N(N), M(M) {
        d.resize(N);
        for (int i = 0; i < N; i++) {
            d[i] = valarray<D>(D(0), M);
        }
    }

    valarray<D>& operator[](int p) {
        return d[p];
    }
    
    const valarray<D>& operator[](int p) const {
        return d[p];
    }
    
    SMatrix& operator=(const SMatrix &other) {
        assert(other.N == N && other.M == M);
        copy_n(other.d.begin(), N, d.begin());
        return *this;
    }

    SMatrix operator+(const SMatrix &right) {
        assert(right.N == N && right.M == M);
        SMatrix res(N, M);
        for (int i = 0; i < N; i++) {
            res[i] = (d[i]+right[i])%MD;
        }
        return res;
    }
    
    SMatrix operator*(const SMatrix &right) {
        assert(M == right.N);
        SMatrix res(N, right.M), r(right.M, right.N);
        for (int i = 0; i < right.M; i++) {
            for (int j = 0; j < right.N; j++) {
                r[i][j] = right[j][i]; 
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < right.M; j++) {
                res[i][j] = (d[i]*r[j]%MD).sum()%MD;
            }
        }
        return res;
    }

    SMatrix operator*(const D x) {
        SMatrix res(N, M);
        for (int i = 0; i < N; i++) {
            res[i] = (d[i]*x)%MD;
        }
        return res;
    }

    SMatrix pow(ll p) {
        assert(N == M);
        SMatrix res(N, M), buf = *this;
        for (int i = 0; i < N; i++) res[i][i] = D(1);
        while(p != 0) {
            if (p % 2) {
                res = res*buf;
            }
            p /= 2;
            buf = buf*buf;
        }
        return res;
    }
    
    void mulL(int i, D x) {
        d[i] *= x;
    }
    
    void excL(int i, int j) {
        swap(d[i], d[j]);
    }
    //line i -> i+(j*x)
    void addL(int i, int j, D x) {
        d[i] += d[j]*x;
    }
    
    int inverse() {
        assert(N == M);
        SMatrix r(N, N);
        for (int i = 0; i < N; i++) r[i][i] = D(1);
        for (int i = 0; i < N; i++) {
            if (d[i][i] == 0) {
                int j;
                for (j = i+1; j < N; j++) {
                    if (abs(d[i][j])) {
                        r.excL(i, j);
                        excL(i, j);
                        break;
                    }
                }
                if (j == N) return i;
            }
            r.mulL(i, 1/d[i][i]);
            mulL(i, 1/d[i][i]);
            for (int j = 0; j < N; j++) {
                if (i == j) continue;
                r.addL(j, i, -d[j][i]);
                addL(j, i, -d[j][i]);
            }
        }
        *this = r;
        return N;
    }
};

//1 1 2 3 5..
ll calc(ll x) {
    SMatrix<MD> s(2, 2);
    s[0][0] = 1;
    s[0][1] = 1;
    s[1][0] = 1;
    s = s.pow(x);
    return s[1][0]+s[1][1];
}
ll solve(ll u, ll k) {
    ll n = (u+1)/2;
    if (k <= (n+1)/2) {
        return calc(u-2*k+2) * calc(1+2*k-2) % MD;
    } else {
        k -= (n+1)/2;
        k = n/2-k+1;
        return calc(u-1-2*k+2) * calc(2+2*k-2) % MD;
    }
}


int main() {
    ll k;
    cin >> k;
    ll u = sqrt(k);
    while (true) {
        if (k <= u*(u+1)) break;
        u++;
    }
    k -= (u-1)*u;
    if (k <= u) {
        printf("%lld\n", solve(u*2-1, k));
    } else {
        printf("%lld\n", solve(u*2, k-u));
    }
    return 0;
}
### Prompt

In Cpp, your task is to solve the following problem:

Example

Input

5


Output

5

### Response

```cpp
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>

using namespace std;
typedef long long ll;

const ll MD = 1e9+7;

template<ll MD>
struct SMatrix {
    typedef ll D;
    vector<valarray<D>> d;
    int N, M;
    SMatrix(int N, int M) : N(N), M(M) {
        d.resize(N);
        for (int i = 0; i < N; i++) {
            d[i] = valarray<D>(D(0), M);
        }
    }

    valarray<D>& operator[](int p) {
        return d[p];
    }
    
    const valarray<D>& operator[](int p) const {
        return d[p];
    }
    
    SMatrix& operator=(const SMatrix &other) {
        assert(other.N == N && other.M == M);
        copy_n(other.d.begin(), N, d.begin());
        return *this;
    }

    SMatrix operator+(const SMatrix &right) {
        assert(right.N == N && right.M == M);
        SMatrix res(N, M);
        for (int i = 0; i < N; i++) {
            res[i] = (d[i]+right[i])%MD;
        }
        return res;
    }
    
    SMatrix operator*(const SMatrix &right) {
        assert(M == right.N);
        SMatrix res(N, right.M), r(right.M, right.N);
        for (int i = 0; i < right.M; i++) {
            for (int j = 0; j < right.N; j++) {
                r[i][j] = right[j][i]; 
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < right.M; j++) {
                res[i][j] = (d[i]*r[j]%MD).sum()%MD;
            }
        }
        return res;
    }

    SMatrix operator*(const D x) {
        SMatrix res(N, M);
        for (int i = 0; i < N; i++) {
            res[i] = (d[i]*x)%MD;
        }
        return res;
    }

    SMatrix pow(ll p) {
        assert(N == M);
        SMatrix res(N, M), buf = *this;
        for (int i = 0; i < N; i++) res[i][i] = D(1);
        while(p != 0) {
            if (p % 2) {
                res = res*buf;
            }
            p /= 2;
            buf = buf*buf;
        }
        return res;
    }
    
    void mulL(int i, D x) {
        d[i] *= x;
    }
    
    void excL(int i, int j) {
        swap(d[i], d[j]);
    }
    //line i -> i+(j*x)
    void addL(int i, int j, D x) {
        d[i] += d[j]*x;
    }
    
    int inverse() {
        assert(N == M);
        SMatrix r(N, N);
        for (int i = 0; i < N; i++) r[i][i] = D(1);
        for (int i = 0; i < N; i++) {
            if (d[i][i] == 0) {
                int j;
                for (j = i+1; j < N; j++) {
                    if (abs(d[i][j])) {
                        r.excL(i, j);
                        excL(i, j);
                        break;
                    }
                }
                if (j == N) return i;
            }
            r.mulL(i, 1/d[i][i]);
            mulL(i, 1/d[i][i]);
            for (int j = 0; j < N; j++) {
                if (i == j) continue;
                r.addL(j, i, -d[j][i]);
                addL(j, i, -d[j][i]);
            }
        }
        *this = r;
        return N;
    }
};

//1 1 2 3 5..
ll calc(ll x) {
    SMatrix<MD> s(2, 2);
    s[0][0] = 1;
    s[0][1] = 1;
    s[1][0] = 1;
    s = s.pow(x);
    return s[1][0]+s[1][1];
}
ll solve(ll u, ll k) {
    ll n = (u+1)/2;
    if (k <= (n+1)/2) {
        return calc(u-2*k+2) * calc(1+2*k-2) % MD;
    } else {
        k -= (n+1)/2;
        k = n/2-k+1;
        return calc(u-1-2*k+2) * calc(2+2*k-2) % MD;
    }
}


int main() {
    ll k;
    cin >> k;
    ll u = sqrt(k);
    while (true) {
        if (k <= u*(u+1)) break;
        u++;
    }
    k -= (u-1)*u;
    if (k <= u) {
        printf("%lld\n", solve(u*2-1, k));
    } else {
        printf("%lld\n", solve(u*2, k-u));
    }
    return 0;
}
```