sol #2：我会矩阵加速了，你知道的

#include <iostream>
#include <cstdio>
#include <memory.h>
#define int long long
#pragma GCC optimize(3)
using namespace std;
const int mod = 1e9 + 7;
int t, n;
int mtx[7][7];
struct matrix{
	int a[7][7];
	matrix(){
		memset(a, 0, sizeof(a));
	}
	void _1(){
		a[0][0] = a[1][0] = a[3][0] = 1;
	}
	void _2(){
		for(int i = 0; i < 7; i++) for(int j = 0; j <= i; j++) a[i][j] = mtx[i][j];//乘数
	}
	matrix operator * (const matrix &b) const{//矩阵乘法
		matrix tmp;
		for(int i = 0; i < 7; i++){
			for(int k = 0; k < 7; k++){
				if(a[i][k] == 0) continue;
				for(int j = 0; j < 7; j++){
					if(b.a[k][j] == 0) continue;
					tmp.a[i][j] += a[i][k] * b.a[k][j];
					tmp.a[i][j] %= mod;
				}
			}
		}
		return tmp;
	}
};

matrix pow(int time){//快速幂
	matrix tmp, a;
	tmp._1();
	a._2();
	while(time){
		if(time & 1) tmp = a * tmp;
		a = a * a, time >>= 1;
	}
	return tmp;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> t;
	mtx[0][0] = 1;
	mtx[1][1] = 1;
	mtx[2][0] = mtx[2][1] = 1, mtx[2][2] = 2;
	mtx[3][3] = 1;
	mtx[4][0] = mtx[4][3] = 1, mtx[4][4] = 2;
	mtx[5][1] = mtx[5][3] = 1, mtx[5][5] = 2;
	mtx[6][2] = mtx[6][4] = mtx[6][5] = 1, mtx[6][6] = 3;
	
	while(t--){
		cin >> n;
		cout << pow(n - 1).a[6][0] << '\n';
	}

	return 0;
}

时间复杂度 $O(TK^3\log N)$，其中 $K=7$。