rt，样例都没过

#include<bits/stdc++.h>
#define INF 2e18
#define endl '\n'
#define PI acos(-1)
#define pb push_back
#define fi first
#define se second
#define int long long
#define mem(x,v) memset(x,v,sizeof x)
using namespace std;
const int N = 105;
const int MOD = 2009;

char s[N];
int n,t;
struct Matrix{
	int a[N][N];
	void init(){mem(a,0);}
}P,Q;

Matrix operator *(const Matrix &x,const Matrix &y){
	Matrix ans;
	ans.init();
	for(int i=1;i<=(n*10);i++)for(int j=1;j<=(n*10);j++)for(int k=1;k<=(n*10);k++)ans.a[i][j]=(ans.a[i][j]+x.a[i][k]*y.a[k][j]%MOD)%MOD;
	return ans;
}

signed main(){
//	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>t,P.init(),Q.init();
	for(int i=1;i<=(n*10);i++)Q.a[i][i]=1;
	for(int i=1;i<=n;i++){
		cin>>s+1;
		for(int j=1;j<=8;j++)P.a[i+j*n][i+(j-1)*n]=1;
		for(int j=1;j<=n;j++)P.a[i][j+n*(s[i]-'1')]=1;
	}
	while(t){
		if(t&1)Q=Q*P;
		P=P*P,t>>=1;
	}
	cout<<Q.a[1][n];
	return 0;
}