记录编号	584688	评测结果	AAAAAAAAAA
题目名称	铺路	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2023-11-14 16:51:01	内存使用	1.15 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//递推 + 矩阵快速幂 
const int mod = 1e9+7;
int t,n;
ll c[6][6];
ll f[6];// 

ll ct[6][6] = {{1,1,0,0,0},{1,0,0,0,0},{2,0,1,0,0},{2,0,1,1,1},{0,0,0,1,0}};
ll ft[6] = {2,0,1,1,1};//初始矩阵 
void first(){
    memcpy(f,ft,sizeof(ft));
    memcpy(c,ct,sizeof(ct));
}// 
void mul(ll x[6],ll y[6][6]){
    ll a[6] = {0};
    for(int j = 0;j < 5;j++){
        for(int k = 0;k < 5;k++){
            a[j] = (a[j] + (x[k] * y[k][j]) % mod) % mod;
        }
    }
    memcpy(x,a,sizeof(a));
} 
void mulself(ll x[6][6]){
    ll a[6][6] = {0};
    for(int i = 0;i < 5;i++){
        for(int j = 0;j < 5;j++){
            for(int k = 0;k < 5;k++){
                a[i][j] = (a[i][j] + (x[i][k] * x[k][j]) % mod) % mod;
            }
        }
    }
    memcpy(x,a,sizeof(a));
}
int main(){
    freopen("obsession.in","r",stdin);
    freopen("obsession.out","w",stdout);
    scanf("%d",&t);
    while(t--){
        first();
        scanf("%d",&n);
        if(n == 1 || n == 2){
            printf("0\n");
            continue;
        }
        int k = n-3;//
        while(k){
            if(k & 1)mul(f,c);
            mulself(c);
            k >>= 1;
        }//快速幂 
        printf("%lld\n",f[0]);
    }
    
    
    return 0;
    
}