设涂到第I块时,颜色A,B都为偶数的数量为ai,一奇一偶的数量为bi,都为奇数为ci, 那么涂到第i+1快时有
a[i+1]=2*a[i]+b[i]+0*c[i];
b[i+1]=2*a[i]+2*b[i]+2*c[i];
C[i+1]=0*a[i]+b[i]+2*c[i];
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long LL;
const int INF=0x4fffffff;
const double EXP=1e-;
const int MS=;
const int SIZE=; const int mod=; typedef vector<vector<int> > mat; // calc A*B mat mul(mat &A,mat &B)
{
mat C(A.size(),vector<int>(B[].size())); for(int i=;i<A.size();i++)
{
for(int k=;k<B.size();k++)
{
for(int j=;j<B[].size();j++)
{
C[i][j]=(C[i][j]+(LL)A[i][k]*B[k][j])%mod; // note overflow
}
}
}
return C;
} // calc A^n mat pow(mat A,LL n)
{
mat B(A.size(),vector<int>(A[].size()));
for(int i=;i<A.size();i++)
B[i][i]=;
while(n>)
{
if(n&)
B=mul(B,A);
A=mul(A,A);
n>>=;
}
return B;
} LL n;
void solve()
{
mat A(,vector<int>());
A[][]=;A[][]=;A[][]=;
A[][]=;A[][]=;A[][]=;
A[][]=;A[][]=;A[][]=;
A=pow(A,n);
printf("%d\n",A[][]);
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
solve();
}
return ;
}