【HZOI/矩阵】#C.迷路

#include
using namespace std;
int n, moyn = 2009, t;
struct matrix{
	long long mat[100][100];
	matrix() {memset(mat,0,sizeof(mat));}
	matrix operator *(const matrix& T) const {
		matrix res;
		int tmp;
		for(int i = 1;i <= 10*9;++i) 
			for(int k = 1;k <= 10*9;++k) {
				tmp = mat[i][k];
				for(int j = 1;j <= 10*9;++j) {//稳定的常数（90^3）时间复杂度的矩阵乘法；
					res.mat[i][j] = res.mat[i][j]+T.mat[k][j]*tmp;
					res.mat[i][j] %= moyn;
				}
			}
		return res;
	}
} in, ans;
void quickpow(int x) {
	while(x) {
		if(x&1) ans = in*ans;
		in = in*in;
		x >>= 1;
	}
	return;
}//一如既往的矩阵快速幂；
void adpoint(int x,int y,int val) {
	if(val == 0) return;
	for(int i = 1;i < val;++i)
		in.mat[x*9+i][x*9+i+1] = 1;
	in.mat[x*9+val][y*9+1] = 1;
	return;
}//本题的关键——拆点；
int main() {
	int tmp;
	scanf("%d %d",&n,&t);
	for(int i = 0;i < n;++i) {
		for(int j = 0;j < n;++j) {
			scanf("%1d",&tmp);//读进一个场宽为1的整形；
			adpoint(i,j,tmp);
		}
	}
	for(int i = 1;i <= n*9;++i)
		ans.mat[i][i] = 1;
	quickpow(t);//也可以为了省事把t换为t-1，同时ans = in；
	printf("%lld",ans.mat[1][(n-1)*9+1]%moyn);
	return 0;
}