快速矩阵幂

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll mod=1e9+7;
int n,m;
struct node{
	ll g[101][101];
}f,res,ans;
void unit(node &x){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i==j) x.g[i][j]=1;
			else x.g[i][j]=0;
}
node cheng(node x,node y){
	node z;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			z.g[i][j]=0;	
	for(int a=1;a<=n;a++)
		for(int b=1;b<=n;b++)
			for(int c=1;c<=n;c++)
				z.g[a][c]=(z.g[a][c]+x.g[a][b]*y.g[b][c])%mod;
	return z;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>f.g[i][j];
	unit(ans);
	while(m){
		if(m&1)ans=cheng(ans,f);
		f=cheng(f,f);
		m=m/2;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			cout<<ans.g[i][j]<<" ";
		cout<<endl;
	}
	return 0;
}