\(f_i\) 仅与 \(f_{i - 1}\) 和 \(f_{i - 2}\) 有关，同时还包括了常数 \(1\)，
所以我们设 \(F_i = \begin{bmatrix} f_{i - 1} & f_{i - 2} & 1 \end{bmatrix}\)，

然后设 \(\text{Base}\) 使得 \(F_{i - 1} \times \text{Base} = F_i\)，
即 \(\begin{bmatrix} f_{i - 2} & f_{i - 3} & 1 \end{bmatrix} \times \text{Base} = \begin{bmatrix} f_{i - 1} & f_{i - 2} & 1 \end{bmatrix}\)。

因为 \(f_{i - 1} = f_{i - 2} + f_{i - 3} + 1\)，所以易知：

\(\text{Base} = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \end{bmatrix}\).

边界条件为 \(F_3 = \begin{bmatrix} 0 & 0 & 1\end{bmatrix}\)，
所以 \(F_{n + 1} = F_3 \times \text{Base}^{n - 2}\)。

即可求出 \(f_n\).

\(f_i\) 仅与 \(f_{i - 1}\)、\(f_{i - 2}\) 和 \(i\) 有关，为实现 \(i\) 的递增，还需设置常量 \(1\)；
所以我们设 \(F_i = \begin{bmatrix} f_{i - 1} & f_{i - 2} & i & 1 \end{bmatrix}\)，

由 \(F_{i - 1} \times \text{Base} = F_i\) 得 \(\text{Base} = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{bmatrix}\).

边界条件为 \(F_3 = \begin{bmatrix} 1 & 0 & 3 & 1 \end{bmatrix}\).

\(F_{n + 1} = F_3 \times \text{Base}^{n - 2}\)；即可求出 \(f_n\)。

我的解法与 OI-Wiki 上的有所不同：

设 \(F_n = \begin{bmatrix} f_{n - 1} & f_{n - 2} & n & 3^n & 1 \end{bmatrix}\).

易知 \(\text{Base} = \begin{bmatrix} 7 & 1 & 0 & 0 & 0 \\ 6 & 0 & 0 & 0 & 0 \\ 5 & 0 & 1 & 0 & 0 \\ 4 & 0 & 0 & 3 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix}\).

边界值 \(F_3 = \begin{bmatrix} 0 & 0 & 3 & 27 & 1 \end{bmatrix}\).

则 \(F_{n + 1} = F_3 \times \text{Base}^{n - 2}\).

增加了 \(f_{i - 3}\)，但是本质是一样的。

可以设 \(F_i = \begin{bmatrix} f_{i - 1} & f_{i - 2} & f_{i - 3} & i & 1 \end{bmatrix}\)，

易得 \(\text{Base} = \begin{bmatrix} 3 & 1 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 5 & 0 & 0 & 1 & 0 \\ 7 & 0 & 0 & 1 & 1 \end{bmatrix}\).

而 \(F_4 = \begin{bmatrix} 1 & 0 & 0 & 4 & 1 \end{bmatrix}\)，

则 \(F_{n + 1} = F_4 \times \text{Base}^{n - 3}\)。

#include <bits/stdc++.h>

#define rr read()

using namespace std;

const long long MOD = 1e9 + 7;

inline int read()
{
    int num = 0, flag = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-')
            flag = -1;
    for (; isdigit(ch); ch = getchar())
        num = (num << 3) + (num << 1) + ch - '0';
    return num * flag;
}

struct matrix
{
    long long a[4][4];
    matrix operator*(const matrix &t) const
    {
        matrix res;
        memset(res.a, 0, sizeof res.a);
        for (int i = 1; i <= 3; ++i)
            for (int j = 1; j <= 3; ++j)
                for (int k = 1; k <= 3; ++k)
                    res.a[i][j] = (res.a[i][j] + a[i][k] * t.a[k][j] % MOD) % MOD;
        return res;
    }
};

int main()
{
    int T = rr;
    while (T--)
    {
        int n = rr;

        if (n <= 3)
        {
            printf("1\n");
            continue;
        }

        matrix Base = {{{0, 0, 0, 0},
                        {0, 1, 1, 0},
                        {0, 0, 0, 1},
                        {0, 1, 0, 0}}};
        matrix res = {{{0, 0, 0, 0},
                       {0, 1, 0, 0},
                       {0, 0, 1, 0},
                       {0, 0, 0, 1}}};

        int k = n - 3;
        while (k)
        {
            if (k & 1)
                res = res * Base;
            k >>= 1, Base = Base * Base;
        }

        printf("%lld\n", (res.a[1][1] + res.a[2][1] + res.a[3][1]) % MOD);
    }

    return 0;
}