题目链接：
设$f[i][j]$表示前$i$列有$j$个$1*1$的格子的方案数，那么可以列出递推式子：
$f[i][0]=f[i-1][0]+f[i-2][0]$
$f[i][1]=2*f[i-1][0]+f[i-1][1]$
$f]i][2]=f[i-1][2]+f[i-2][2]+f[i-2][1]$
通过递推式子求出一个$6*6$的矩阵然后用矩阵乘法优化递推即可。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int mod=1e9+7;
struct lty
{
int a[7][7];
lty(int x)
{
memset(a,0,sizeof(a));
for(int i=1;i<=6;i++)
{
a[i][i]=x;
}
}
lty operator *(lty s)
{
lty res(0);
for(int i=1;i<=6;i++)
{
for(int j=1;j<=6;j++)
{
for(int k=1;k<=6;k++)
{
res.a[i][j]=(res.a[i][j]+1ll*a[i][k]*s.a[k][j]%mod)%mod;
}
}
}
return res;
}
};
int n,T;
lty quick(int k)
{
lty f(0);
f.a[1][1]=1,f.a[4][1]=1;
f.a[1][2]=2,f.a[2][2]=1;
f.a[3][3]=1,f.a[5][3]=1;
f.a[6][3]=1,f.a[1][4]=1;
f.a[2][5]=1,f.a[3][6]=1;
lty g(1);
if(k<0)
{
return g;
}
while(k)
{
if(k&1)
{
g=g*f;
}
k>>=1;
f=f*f;
}
return g;
}
void solve(int n)
{
lty res=quick(n-2);
int ans=1ll*res.a[1][3]*2%mod;
ans=(ans+1ll*res.a[2][3]*4%mod)%mod;
ans=(ans+1ll*res.a[4][3]*1%mod)%mod;
ans=(ans+1ll*res.a[5][3]*2%mod)%mod;
printf("%d\n",ans);
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
solve(n);
}
}