Lick the dog until the last one has nothing (state machine)

Title Description
As the core of the team ,forever97 He is respected by the other two teammates .
Trote_w Please... Every day forever97 Take out , But unfortunately, the center of the universe forever97 There are only 3 home forever97 Favorite takeout .
If Trote_w to forever97 Bought takeout from another family ,forever97 Will shout “ I don't eat I don't eat ”.
however forever97 I don't like to eat a takeout for three days in a row .
If Trote_w One day I forgot about it and bought him the same takeout for three days , that forever97 It will Trote_w Press your head into the screen of your mobile phone .
As Trote_w Good friends , You can tell him to keep asking forever97 eat n Tianfan , How many different ways to buy ？

Input description :
Multiple sets of samples
The first line is an integer T(1<=T<=20) Represents the number of test samples
Next t Each row is an integer n, representative Trote_w Please forever97 eat n Tianfan (1<=n<=100000)

Output description :
Output T An integer represents the number of schemes , Because the answer is too big , You just need to output mod 1e9+7 The answer after .
Example 1
Input

2
3
500
Output

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;
	}
}