样例没有过

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;

int a[3][3] = {
	{0, 1, 0},
	{0 ,0, 1},
	{1, 0, 1}
};

int f[3][3] = {1, 1, 1};

inline void Mul (int f[3][3], int x[3][3], int y[3][3]) {
	int t[3][3];
	
	for (int i = 0; i < 3; i ++) {
		for (int j = 0; j < 3; j ++) {
			t[i][j] = 0;
		}
	}
	
	for (int i = 0; i < 3; i ++) {
		for (int j = 0; j < 3; j ++) {
			for (int k = 0; k < 3; k ++) {
				t[i][j] = (t[i][j] + 1ll * x[i][k] * y[k][j]) % mod;
			}
		}
	}
	
	for (int i = 0; i < 3; i ++) {
		for (int j = 0; j < 3; j ++) {
			f[i][j] = t[i][j];
		}
	}
}

int n;

int main () {
	int T;
	
	cin >> T;
	
	while (T --) {
		cin >> n;
	
		for (int i = n - 3; i; i >>= 1) {
			if (i & 1) {
				Mul (f, f, a);
			}
			
			Mul (a, a, a);
		}
		
		cout << f[0][2] % mod << endl;
	} 
	
	return 0;
}

和 这篇 思路相似

求各位大佬调调