Lick the dog until the last one has nothing (simple DP)

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

analysis ：

about a,b,c Three takeaways , Hypothesis number 1 i God eat a, Then the number of schemes is i-1 God eat a+ The first i-1 God eat b+ The first i-1 God eat c;

Among them the first i-1 God eat a when , The first i-2 It's impossible to eat a, Can only eat b or c.

So the first i God eat a Number of schemes Actually, it is No i-2 God eat b+ The first i-2 God eat c+ The first i-1 God eat b+ The first i-1 God eat c;

The same goes for the other two takeout .

The first i God eat b Number of schemes Actually, it is No i-2 God eat a+ The first i-2 God eat c+ The first i-1 God eat a+ The first i-1 God eat c;

The first i God eat c Number of schemes Actually, it is No i-2 God eat a+ The first i-2 God eat b+ The first i-1 God eat a+ The first i-1 God eat b;

All in all , The first i Number of prescriptions = The first i-2 Number of prescriptions *2+ The first i-1 Number of prescriptions *2;

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int f[100010];
int main()
{
	int T;
	cin >> T;
	f[1] = 3, f[2] = 9;
	while (T--) {
		int x;
		cin >> x;
		for (int i = 3; i <= x; i++) f[i] = (f[i - 1] + f[i - 2]) % mod * 2 % mod;
		cout << f[x] << endl;
	}
	return 0;
}