ACM-ICPC 2018 Jiaozuo Cyber ​​Pre-Position Poor God Water

God Water likes to eat meat, fish and chocolate very much, but unfortunately, the doctor tells him that some sequence of eating will make them poisonous.

Every hour, God Water will eat one kind of food among meat, fish and chocolate. If there are 3 continuous hours when he eats only one kind of food, he will be unhappy. Besides, if there are 3 continuous hours when he eats all kinds of those, with chocolate at the middle hour, it will be dangerous. Moreover, if there are 3 continuous hours when he eats meat or fish at the middle hour, with chocolate at other two hours, it will also be dangerous.

Now, you are the doctor. Can you find out how many different kinds of diet that can make God Water happy and safe during NN hours? Two kinds of diet are considered the same if they share the same kind of food at the same hour. The answer may be very large, so you only need to give out the answer module 1000000007.

Input

The fist line puts an integer T that shows the number of test cases. (T≤1000)

Each of the next T lines contains an integer NNthat shows the number of hours. (1≤N≤1010)

Output

For each test case, output a single line containing the answer.

样样输入Copy

3
3
4
15

样出出Copy

20
46
435170

题源

题意:有肉, Fish, chocolate three kinds of food, there are several taboos, for three consecutive foods, 1. These three foods can not be the same; 2. If all three foods, chocolate can not be in the middle; 3. If both sides are Chocolate, the middle can not be meat or fish, the number of programs

分析: The first one is recursively enumerated, 1, 2, 3 (2 is chocolate) but found to be recursive too much. The last two enumerations, 11, 12, 13, 21, ....

f(i, j, k): indicates the i-th hour, the last penultimate is j, the last one The bit is k.

则f(i,1,1)=f(i-1,2,1)+f(i-1,3,1)

. . . (There are 8 recursions left)

#include<bits/stdc++.h>
using namespace std;
 
#define e exp(1)
#define pi acos(-1)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define ll long long
#define ull unsigned long long
#define mem(a,b) memset(a,b,sizeof(a))
int gcd(int a,int b){return b?gcd(b,a%b):a;}

const int N=9;
ll n;
struct mat
{
    ll a[N][N];
};
mat mat_mul(mat x,mat y)  
{
    mat res;  
    mem(res.a,0);  
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) 
        for(int k=0;k<N;k++)
        res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
    return res;
}
void mat_pow(ll n)
{
    mat c,res;
    mem(c.a,0);
    
    c.a[0][3]=c.a[0][6]=1;
    c.a[1][0]=c.a[1][6]=1;
    c.a[2][0]=c.a[2][3]=c.a[2][6]=1;
    c.a[3][1]=c.a[3][4]=1;
    c.a[4][1]=c.a[4][7]=1;
    c.a[5][4]=c.a[5][7]=1;
    c.a[6][2]=c.a[6][5]=c.a[6][8]=1;
    c.a[7][2]=c.a[7][8]=1;
    c.a[8][2]=c.a[8][5]=1;
    
    mem(res.a,0);
    for(int i=0;i<N;i++) res.a[i][i]=1;  
    while(n)
    {
        if(n&1) res=mat_mul(res,c);  
        c=mat_mul(c,c);  
        n>>=1;
    }
    
    //res.a
    ll ans=0;
    for(int i=0; i<N; i++)
    {
    	for(int j=0; j<N; j++)
    	{
    		ans=(ans+res.a[i][j])%mod;
		}
	}
	printf("%lld\n",ans);
}
int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		scanf("%lld",&n);
		if(n==1)puts("3");
		else if(n==2)puts("9");
		else
		{
			mat_pow(n-2);
		}
	}
	return 0;
}