这是我这题的代码：

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
struct mtrx{
	int n,m;
	long long num[114][114];
	mtrx(int r,int c){
		memset(num,0,sizeof(num));
		n=r;
		m=c;
	}
	mtrx(int nm){
		memset(num,0,sizeof(num));
		n=m=nm;
		for(int i=1;i<=n;++i) num[i][i]=1;
	}
};
mtrx operator * (mtrx x,mtrx y){
	mtrx z(x.n,y.m);
	for(int i=1;i<=z.n;++i){
		for(int j=1;j<=z.m;++j){
			for(int k=1;k<=x.m;++k){
				z.num[i][j]=(z.num[i][j]+((x.num[i][k]*y.num[k][j])%mod))%mod;
			}
		}
	}
	return z;
}
mtrx mtpow(mtrx x,long long k){
	mtrx res(x.n);
	while(k){
		if(k&1) res=res*x;
		x=x*x;
		k>>=1;
	}
	return res;
}
int main(){
	int T;
	cin>>T;
	while(T--){
		long long n;
		cin>>n;
		if(n<4){
			cout<<1<<endl;
			continue;
		}
		else{
			mtrx a(4,4);
			a.num[1][1]=a.num[1][2]=a.num[1][3]=a.num[1][4]=a.num[2][2]=a.num[2][3]=a.num[3][1]=a.num[3][3]=a.num[3][4]=a.num[4][1]=a.num[4][2]=1;
			a.num[2][1]=a.num[2][4]=a.num[3][2]=a.num[4][3]=a.num[4][4]=1;
			mtrx b(1,4);
			b.num[1][1]=1;
			b.num[1][2]=1;
			b.num[1][3]=1;
			b.num[1][4]=2;
			mtrx res=mtpow(a,n-4);
			mtrx ans=b*res,kkk=b*a;
			cout<<ans.num[1][4]<<endl;
		}
	}
	return 0;
}

原理和我的P1962斐波那契数列代码类似。
此题代码计算最后ans矩阵应该为第n-3~n位，但是在调试时，输出代码中的矩阵kkk时，发现kkk四位全为5，而kkk四位本应分别为数列第2~5个数。在类似思路的斐波那契数列代码AC的情况下，我未能理解这题我的代码错误，故请大佬指出，玄关！