舔狗舔到最后一无所有（状态机）

题目描述
作为队伍的核心，forever97很受另外两个队友的尊敬。
Trote_w每天都要请forever97吃外卖，但很不幸的是宇宙中心forever97所在的学校周围只有3家forever97爱吃的外卖。
如果Trote_w给forever97买了别家的外卖，forever97就会大喊“我不吃我不吃”。
但是forever97又不喜欢连续三天吃一种外卖。
如果Trote_w哪天忘了这件事并且三天给他买了同一家外卖，那么forever97就会把Trote_w的头摁进手机屏幕里。
作为Trote_w的好朋友，你能告诉他连续请forever97吃n天饭，有多少不同的购买方法吗？

输入描述:
多组样例
第一行一个整数T(1<=T<=20)代表测试样例数
接下来t行每行一个整数n，代表Trote_w要请forever97吃n天饭(1<=n<=100000)

输出描述:
输出T个整数代表方案数，由于答案太大，你只需要输出mod 1e9+7 后的答案即可。
示例1
输入

2
3
500
输出

24
544984352

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
ll dp[2][100000+10];
int main()
{     ll n,t; cin>>t;
	dp[0][1]=3; dp[1][0]=0;
	
	for(int i=2;i<=100000+10;i++)
	{
		dp[0][i]=(dp[1][i-1]*2+dp[0][i-1]*2)%M;
		dp[1][i]=dp[0][i-1]%M;
	}
	
	while(t--)
	{  cin>>n;
		
		cout<<(dp[0][n]%M+dp[1][n]%M)%M<<endl;
	}
}