矩阵乘法模板--zhengjun
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;
}
};