样例TLE，求大佬们改改

#include<bits/stdc++.h>
#define int unsigned long long
//typedef long long int
using namespace std;
const int maxN = 4;
const int Mod = 1e9 + 7; 
struct mat{int m[maxN][maxN];}unit;
inline int read(){
	int s = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-')f = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
inline void write(int x){
	if(x < 0)putchar('-'), x = -x;
	if(x >= 10)write(x / 10);
	putchar(x % 10 + '0');
}
void init(){
	for(int i = 1; i <= maxN; i++)unit.m[i][i] = 1;
}
mat operator * (const mat &a, const mat &b){
	mat ans;
	for(int i = 1; i <= maxN; i++){
		for(int j = 1; j <= maxN; j++){
			int tmp = 0;
			for(int k = 1; k <= maxN; k++){
				tmp = (tmp + a.m[i][k] * b.m[k][i]) % Mod;
			}
			ans.m[i][j] = tmp;
		}
	}
	return ans;
}
mat mat_quick_multi(mat a, int b){
	init();
	mat ans = unit;
	while(b){
		if(b & 1)ans = (ans * a);
		a = (a * a);
		b >>= 1;
	}
	return ans;
}

signed main()
{
	mat a;
	a.m[1][1] = 1; a.m[2][1] = 1; a.m[3][1] = 0;
	a.m[1][2] = 0; a.m[2][2] = 0; a.m[3][2] = 1;
	a.m[1][3] = 1; a.m[2][3] = 0; a.m[3][3] = 0;
	int T = read();
	while(T--){
		int n = read();
		if(n <= 3){
			cout << 1;
			continue;
		}
		mat ans1 = mat_quick_multi(a, n - 3);
		printf("%lld", (ans1.m[1][1] + ans1.m[1][2]) % Mod);
	}
	return 0;
}