不开O2就过了，开了O2就全RE了

救了个大命Olo

#include<bits/stdc++.h>
#define ls(x) son[x][0]
#define rs(x) son[x][1]
#define ll long long
using namespace std;

const int MAXN = 100;
const int MOD = 2009;

int inpt()
{
	int x = 0, f = 1;
	char ch;
	for(ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
	if(ch == '-'){
		f = -1;
		ch = getchar();
	}
	do{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}while(ch >= '0' && ch <= '9');
	return x * f;
}

int n, t;
int mp[MAXN][MAXN];

int GetPos(int i, int j)
{
	return i + n * j;
}

struct Matrix {
	int mat[MAXN][MAXN];
	int h, l;
	
	Matrix() {
		memset(mat, 0, sizeof(mat));
	}
	
	Matrix operator * (const Matrix &qwq) const {
		if(l == qwq.h) {
			Matrix val;
			val.h = h, val.l = qwq.l;
			
			for(int i = 1; i <= h; i++) {//这道题0是有单独意义的 
				for(int j = 1; j <= qwq.l; j++) {
					int &tmp = val.mat[i][j];
					for(int k = 1; k <= l; k++) {
						tmp = (tmp + 1ll * mat[i][k] * qwq.mat[k][j] % MOD) % MOD;
					}
				}
			}
			
			return val;
		}
	}
	
	void Identify() {
		h = 9 * n, l = 9 * n;
		for(int i = 1; i <= 9 * n; i++) {
			mat[i][i] = 1;
		}
	}
	
//	void GetChangeMatrix() {
//		h = n, l = n;
//		
//		for(int i = 1; i <= n; i++) {
//			for(int j = 1; j <= n; j++) {
//				mat[i][j] = mp[j][i];//这里都要和原邻接矩阵相反 
//			}
//		}
//	}

	void GetChangeMatrix() {
		h = 9 * n, l = 9 * n;
		
		
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= 8; j++) {
				mat[GetPos(i, j - 1)][GetPos(i, j)] = 1;//这里都要和原邻接矩阵相反
			}
			char ch[11];
			scanf("%s", ch + 1);
			for(int j = 1; j <= n; j++) {
				if(ch[j]) {
					mat[GetPos(j, ch[j] - '0' - 1)][GetPos(i, 0)] = 1;
				}//记得一定要减一 
			}
		}
	}
	
	void GetBeginMatrix() {
		h = 9 * n, l = 1;
		mat[1][1] = 1;
	}
	
	Matrix operator ^ (const int &yy) const {
		Matrix val;
		val.Identify();
		Matrix x = *this;
		int y = yy;
		while(y) {
			if(y & 1)
				val = val * x;
			x = x * x;
			y >>= 1;
		}
		return val;
	}
}beg, cg;

int main()
{
	n = inpt(), t = inpt();
	cg.GetChangeMatrix();
	
	beg.GetBeginMatrix();
	
	cg = cg ^ t;
	beg = cg * beg;
	
	printf("%d", beg.mat[n][1]);
	
	return 0;
}