神仙溢出未解之谜

#include<iostream>
#include<cstring>
using namespace std;
const int mod=10000007;
struct Matrix
{
	int n,m;
	int sum[50][50];
	void clear()
	{
		memset(sum,0,sizeof(sum));
	}
	friend Matrix operator * (Matrix a,Matrix b)
	{
		Matrix c;
		c.n=a.n,c.m=b.m;
		for(int i=1;i<=c.n;i++)
		{
			for(int j=1;j<=c.m;j++)
			{
				int t=0;
				for(int k=1;k<=a.m;k++)
				{
					t+=a.sum[i][k]*b.sum[k][j];
				}
				c.sum[i][j]=t;
			}
		}
		return c;
	}
	friend Matrix operator + (Matrix a,Matrix b)
	{
		Matrix c;
		c.n=a.n;
		c.m=a.m;
		for(int i=1;i<=a.n;i++)
		{
			for(int j=1;j<=a.m;j++)
			{
				c.sum[i][j]=(a.sum[i][j]+b.sum[i][j])%mod;
			}
		}
		return c;
	}
	friend Matrix operator % (Matrix a,int d)
	{
		Matrix c;
		c.n=a.n,c.m=a.m;
		for(int i=1;i<=a.n;i++)
		{
			for(int j=1;j<=a.m;j++)
			{
				c.sum[i][j]=a.sum[i][j]%d;
			}
		}
		return c;
	}
};
Matrix qpow(Matrix a,int p)
{
	Matrix ret;
	ret.clear();
	ret.n=ret.m=a.n;
	for(int i=1;i<=ret.n;i++)
	{
		ret.sum[i][i]=1;
	}
	while(p)
	{
		if(p&1)
		{
			ret=ret*a%mod;
		}
		p>>=1;
		a=a*a%mod;
	}
	ret=ret%mod;
	return ret;
}
int main()
{
	int T;
	cin >> T;
	Matrix t,c;
	t.n=t.m=3;
	t.sum[1][1]=t.sum[1][3]=t.sum[2][1]=t.sum[3][2]=1;
	c.n=3,c.m=1;
	c.sum[1][1]=1,c.sum[2][1]=1,c.sum[3][1]=1;
	Matrix ans;
	while(T--)
	{
		int n;
		cin >> n;
		if(n<=3)
		{
			cout << 1 << '\n';
			continue;
		}
		ans.clear();
		ans=qpow(t,n-3);
//		for(int i=1;i<=3;i++)
//		{
//			for(int j=1;j<=3;j++)
//			{
//				cout << ans.sum[i][j] << ' ';
//			}
//			cout << '\n';
//		}
		ans=ans*c;
		cout << ans.sum[1][1] << '\n';
	}	
	return 0;
}