矩阵乘法模板--zhengjun-526互联

struct matrix{
	int a[M][M];
	matrix(){
		memset(a,0,sizeof a);
	}
	matrix operator * (const matrix &x)const{
		matrix b;
		for(int k=0;k<m;k++)
			for(int i=0;i<m;i++)
				for(int j=0;j<m;j++)
					b.a[i][j]=(b.a[i][j]+1ll*a[i][k]*x.a[k][j])%mod;
		return b;
	}
};
struct vec{
	int a[M];
	vec(){
		memset(a,0,sizeof a);
	}
	vec operator * (const matrix &x)const{
		vec b;
		for(int i=0;i<m;i++)
			for(int j=0;j<m;j++)
				b.a[j]=(b.a[j]+1ll*a[i]*x.a[i][j])%mod;
		return b;
	}
};