因此，若要求数列的第 $n$ 项，只要令 $V = A^nV$，此时 $V$ 的第一个元素就是答案了。其中 $A^n$ 可以用矩阵快速幂求出来，时间复杂度为 $O(logn)$。矩阵快速幂和普通快速幂几乎一样，只是把乘法改为了矩阵乘法。在初始化结果时，普通快速幂应初始化为 $1$，矩阵快速幂则应初始化为单位矩阵 $I$。
---
本题解给出 python 代码，可以直接将二维 ```list``` 作为函数的参数和返回值。如果用 c++，由于二维数组作为参数和返回值时比较麻烦，一个简单的方法是把矩阵封装为结构体，然后将该结构体作为函数的参数与返回值即可。
代码如下（python）：
```python
import sys
MOD = 1e9 + 7
MOD = int(MOD)
# 矩阵乘法，传入两个矩阵 a 和 b，返回矩阵乘法 a*b 得到的结果矩阵
def matmul(a, b):
if len(a[0]) != len(b): # a 的列 != b 的行，乘不了
sys.stderr.write("size error\n")
sys.exit(1)
row = len(a) # 结果的行是 a 的行
col = len(b[0]) # 结果的列是 b 的列
tmp = len(b) # a 的列 || b 的行，即共享维度
result = [[0 for _ in range(col)] for _ in range(row)]
for i in range(row):
for j in range(col):
for k in range(tmp):
result[i][j] += a[i][k] * b[k][j]
result[i][j] %= MOD
return result
# 矩阵快速幂，a 为矩阵，b 为要求的次幂
def quick_pow(a, b):
row = len(a)
col = len(a[0])
# 结果初始化为单位矩阵（直接用列表生成式即可生成单位矩阵，内层的那部分式子相当于三目运算符）
result = [[1 if i == j else 0 for j in range(col)] for i in range(row)]
while b > 0:
if b & 1:
# 矩阵乘法一般不满足交换律，但由于 result 是 a 的整数次幂，根据结合律 a 乘在哪边都行
# 不过我们进行线性变换是左乘，所以乘在左边更符合直觉
result = matmul(a, result)
b >>= 1
a = matmul(a, a)
return result
matrix = [[0, 1, 0, 0], # 单次线性变换对应的矩阵
[0, 0, 1, 0],
[0, 0, 0, 1],
[0, 1, 0, 1]]
vector = [[0], # 初始列向量
[1],
[1],
[1]]
T = int(input())
while T > 0:
n = int(input()) # n 代表矩阵是几次幂，不能取模，一开始铸币取模了
change = quick_pow(matrix, n) # 用矩阵快速幂得到 n 次变换对应的矩阵
result = matmul(change, vector) # 将变换利用矩阵乘法应用到初始列向量上
print(result[0][0])
T -= 1
```