矩阵快速幂90分求调（AC必关注）

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
struct matrix
{
	int a[5][5];
};
matrix mul (matrix x,matrix y)
{
	matrix c;
	memset(c.a,0,sizeof c.a);
	for(int i=1;i<=4;i++)
	for(int j=1;j<=4;j++)
	for(int k=1;k<=4;k++)
	c.a[i][j]=(c.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
	return c;
}
matrix quickpow (matrix x,int n)
{
	matrix res;
	memset(res.a,0,sizeof res.a);
	res.a[1][1]=1;
	res.a[1][2]=1;
	res.a[1][3]=1;
	res.a[1][4]=2; 
	while(n>0)
	{
		if(n&1) res=mul(res,x);
		x=mul(x,x);
		n>>=1;
	}
	return res;
}
signed main()
{
	int t,n;
	cin>>t;
	while(t--)
	{
		cin>>n;
		if(n<4) cout<<1<<endl;
		else if(n==4) cout<<4<<endl;
		else{
		matrix x;
		memset(x.a,0,sizeof x.a);
		x.a[2][1]=1;
		x.a[2][4]=1;
		x.a[3][2]=1;
		x.a[4][3]=1;
		x.a[4][4]=1;
		x=quickpow(x,n-4);
		cout<<x.a[1][4]%mod<<endl;
        }
	}
	return 0; 
}