思路：长度恰好为 $n$ 时有 $F_n$ 种，问题变为对斐波那契数列求和。

转移矩阵为

$\begin{bmatrix}0&1&0\\1&1&0\\1&1&1\end{bmatrix}\begin{bmatrix}F_{i-2}\\F_{i-1}\\S_{i-1}\end{bmatrix}=\begin{bmatrix}F_{i-1}\\F_{i-2}+F_{i-1}\\F_{i-2}+F_{i-1}+S_i\end{bmatrix}$

代码（可过样例）：

#include <cstdio>

using namespace std;

class matrix33
{
public:
	unsigned long long
		a, b, c,
		d, e, f,
		g, h, i;
	matrix33(
		unsigned long long a, 
		unsigned long long b, 
		unsigned long long c, 
		unsigned long long d, 
		unsigned long long e, 
		unsigned long long f,
		unsigned long long g, 
		unsigned long long h, 
		unsigned long long i)
	{
		this->a = a % 1000000007;
		this->b = b % 1000000007;
		this->c = c % 1000000007;
		this->d = d % 1000000007;
		this->e = e % 1000000007;
		this->f = f % 1000000007;
		this->g = g % 1000000007;
		this->h = h % 1000000007;
		this->i = i % 1000000007;
	}
	friend matrix33 operator*(const matrix33& x, const matrix33& y)
	{
		return {
			x.a * y.a + x.b * y.d + x.c * y.g, x.a * y.b + x.b * y.e + x.c * y.h, x.a * y.c + x.b * y.f + x.c * y.i,
			x.d * y.a + x.e * y.d + x.f * y.g, x.d * y.b + x.e * y.e + x.f * y.h, x.d * y.c + x.e * y.f + x.f * y.i,
			x.g * y.a + x.h * y.d + x.i * y.g, x.g * y.b + x.h * y.e + x.i * y.h, x.g * y.c + x.h * y.f + x.i * y.i
		}; // 这里为了加速牺牲了亿点点可读性，是三阶矩阵乘法的展开。
	}
};

template<typename T>
T qpow(const T& x, unsigned long long y)
{
	if (y == 1) return x;
	T res = qpow(x, y >> 1);
	res = res * res;
	if (y & 1) res = res * x;
	return res;
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		long long n;
		scanf("%lld", &n);
		if (n == 1)
		{
			printf("1\n");
			continue;
		}
		matrix33 res = qpow<matrix33>({ 0, 1, 0, 1, 1, 0, 1, 1, 1 }, n - 1);
		printf("%llu\n", (res.g + res.h + 2 * res.i + 1000000006) % 1000000007);
	}
	return 0;
}