矩阵写法

template<int N,int M,class T = long long>
struct matrix {
	int m[N][M];
	matrix(){memset(m,0,sizeof(m));}
	void init(){for(int i = 0;i < N;i++) m[i][i] = 1;}
	friend bool operator != (matrix<N,M> x,matrix<N,M> y) {
		for(int i = 0;i<N;i++)
			for(int j = 0;j<M;j++)
				if(x[i][j] != y[i][j])
					return true;
		return false;
	}
	int* operator [] (const int pos) {return m[pos];}
	void print(string s) {
		cout<<'\n';
		string t = "test for " + s + " matrix:";
		cout<<t<<'\n';
		for(int i = 0;i<N;i++)
			for(int j = 0;j<M;j++)
				cout<<m[i][j]<<" \n"[j == M - 1];
		cout<<'\n';
	}
};
template<int N,int M,int R,class T = long long>
matrix<N,R,T> operator * (matrix<N,M,T> a,matrix<M,R,T> b) {
	matrix<N,R,T> c;
	for(int i = 0;i<N;i++)
		for(int j = 0;j<M;j++)
			for(int k = 0;k<R;k++)
				c[i][k] = c[i][k] + a[i][j] * b[j][k];
	return c;
}
template<int N,int M,class T = long long>
matrix<N,M,T> operator + (matrix<N,M,T> a,matrix<N,M,T> b) {
	for(int i = 0;i<N;i++)
		for(int j = 0;j<M;j++)
			a[i][j] += b[i][j];
	return a;
}
template<int N,class T = long long>
matrix<N,N,T> qpow(matrix<N,N,T> x,int k) {
	matrix<N,N,T> re;
	re.init();
	while(k){
		if(k & 1) re = re * x;
		x = x * x;
		k >>= 1;
	}
	return re;
}