萌新求助玄学问题

#include<iostream>
#include<cstring>

using namespace std;

struct Matrix{
	long long val[109][109];
	int line,cell;
};

const long long p = 1e9+7;

Matrix unit(int size){
	Matrix m;
	m.line=m.cell=size;
	for(int i=0; i<size; i++){
		m.val[i][i]=1;
	}
	return m;
}

void DisplayMatrix(Matrix a){
	cout<<"Displaying matrix"<<endl;
	cout<<a.line<<' '<<a.cell<<endl;
	for(int i=0; i<a.line; i++){
//		cout<<"Displaying line "<<i<<endl;
		for(int j=0; j<a.cell; j++){
			cout<<a.val[i][j]<<' ';
		}cout<<endl;
	}
}

Matrix mul(Matrix a,Matrix b){//c[i][j] = sum(a[i][k]*b[k][j])
	if(a.cell != b.line){
		cout<<"Matrix mul error: a.cell != b.line"<<endl;
//		cout<<a.line<<' '<<a.cell<<' '<<b.line<<' '<<b.cell;
		DisplayMatrix(a);
		DisplayMatrix(b);
	}
	
	Matrix c;
	c.line = a.line;
	c.cell = b.cell;
	memset(c.val,0,sizeof(c.val));
	
//	cout<<"MULing: "<<endl;
//	DisplayMatrix(a);
//	DisplayMatrix(b);
	
	for(int i=0; i<a.line; i++){
		for(int j=0; j<b.cell; j++){
//			cout<<"Muling: "<<i<<' '<<j<<endl;
			for(int k=0; k<a.cell; k++){
//				cout<<"K: "<<k<<endl;
				c.val[i][j] += (a.val[i][k]%p)*(b.val[k][j]%p);
				c.val[i][j] %= p;
//				cout<<"Added "<<a.val[i][k]*b.val[k][j]<<endl;
			}
//			cout<<"MUl: "<<i<<' '<<j<<" "<<c.val[i][j]<<endl;
		}
	}
//	cout<<"Matrix c:"<<endl;
//	DisplayMatrix(c);
	return c;
}

Matrix qPow(Matrix Base,long long z){
	Matrix ans = unit(Base.line);
//	DisplayMatrix(Base);
	while(z){
		
		if(z&1)ans = mul(ans,Base);
		Base = mul(Base,Base);
		z>>=1;
//		cout<<"Qpowing "<<endl;
//		DisplayMatrix(ans);
	}
//	cout<<"Qpow: "<<ans.line<<" "<<ans.cell<<endl;
	return ans;
}

long long n,k;

int T;

int main(){
	cin>>T;
	while(T--){
		cin>>n;
		Matrix fibo;
		fibo.line = fibo.cell = 3;
		fibo.val[0][0]=1; fibo.val[0][1]=0; fibo.val[0][2]=1;
		fibo.val[1][0]=1; fibo.val[1][1]=0; fibo.val[1][2]=0;
		fibo.val[2][0]=0; fibo.val[2][1]=1; fibo.val[2][2]=0;
	
		fibo = qPow(fibo,n);
	
//		Matrix ans;
//		ans.line=3; ans.cell = 1;
//		ans.val[0][0] = 1;
//		ans.val[1][0] = 1;
//		ans.val[2][0] = 1;
//		ans = mul(fibo,ans);
	
//		DisplayMatrix(fibo);
//		DisplayMatrix(ans);
	
		cout<<fibo.val[1][0]%p<<endl;
	}
	
	
	return 0;
}