矩阵快速幂（Python）

思路：斐波那契数列变种，矩阵快速幂优化。观察题目的数据量可知，这题我们需要用到矩阵快速幂进行优化。首先写两个函数：1.矩阵乘法函数mat_mul、2.矩阵快速幂函数mat_pow。由于本题的斐波那契数列递推比一般的斐波那契数列递推用到的数要更前一位，所以说就需要用到3维的递推矩阵

接着对3维递推矩阵进行矩阵快速幂操作，其幂次为。为什么？因为从索引0开始算起，那就有，有这三个基本数据，就可以推出后面的。因此，最大的基本数据索引为，那我们要推到，就只需要走步即可。此时的答案就是数组第一行向量，也就是，然后把答案添加到out数组中，最终整体输出即可

代码：

import sys
input = lambda: sys.stdin.readline().strip()

import math
inf = 10 ** 18

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return input().split()

def LII():
    return list(map(int, input().split()))

def LFI():
    return list(map(float, input().split()))

fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
isqrt = lambda x: int(math.sqrt(x))

'''

'''

def mat_mul(A, B, mod):
    n = len(A)
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            res[i][j] = sum(A[i][k] * B[k][j] for k in range(n)) % mod
    return res

def mat_pow(M, n, mod):
    res = [[1, 0, 0],
           [0, 1, 0],
           [0, 0, 1]]
    base = [row[:] for row in M]
    while n > 0:
        if n & 1:
            res = mat_mul(res, base, mod)
        base = mat_mul(base, base, mod)
        n >>= 1
    return res

out = []

def solve():
    mod = 10 ** 9 + 7
    n = II()

    if n == 1 or n == 2:
        print(1)
        return

    M = [[1, 0, 1],
         [1, 0, 0],
         [0, 1, 0]]

    res = mat_pow(M, n - 2, mod)
    ans = (res[0][0] * 1 + res[0][1] * 1 + res[0][2] * 0) % mod
    out.append(str(ans))

# t = 1
t = II()
for _ in range(t):
    solve()

print('\n'.join(out))