记录编号	601120	评测结果	AAAAAAAAAA
题目名称	3108.[GXOI/GZOI2019]逼死强迫症	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	0.062 s
提交时间	2025-06-03 10:40:23	内存使用	3.86 MiB

#include <bits/stdc++.h>
using namespace std;

const int md=1e9+7;
typedef long long LL;

struct jz{
    int a[5][5];
    inline jz(){memset(a,0,sizeof a);}
    inline jz operator*(const jz&b)const{
        jz c;
        for(int i=0;i<5;++i)
            for(int k=0;k<5;++k)
                for(int j=0;j<5;++j)
                    c.a[i][j]=(c.a[i][j]+(LL)a[i][k]*b.a[k][j])%md;
        return c;
    }
};

jz pow(jz a,int b){
    jz ret;
    ret.a[0][0]=ret.a[1][1]=ret.a[2][2]=ret.a[3][3]=ret.a[4][4]=1;
    for(;b;b>>=1,a=a*a)
        if(b&1)ret=ret*a;
    return ret;
}

int main(){
	freopen("obsession.in","r",stdin);
	freopen("obsession.out","w",stdout);
	jz s;
    s.a[0][1]=s.a[1][0]=s.a[1][1]=s.a[2][3]=s.a[3][2]=s.a[3][3]=s.a[4][4]=1;
    s.a[3][1]=2,s.a[4][1]=md-1;
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        if(n<3)
            puts("0");
        else{
            jz ans;
            ans.a[0][2]=1,ans.a[0][3]=ans.a[0][4]=2;
            printf("%d\n",(ans*pow(s,n-2)).a[0][1]);
        }
    }
    return 0;
}