题目和普通的 (01) 路径矩阵加速有一点区别，做法很巧。
(large{ exttt{Meaning}})
给定一个邻接矩阵，即每个点之间的边权，若为 (0) 则无边，因为是 (a*a) 的矩阵，所以隐藏含义是每条边权 (1)~(9) 。
(large{ exttt{Solution}})
因为边权不只是 (1) 了，所以不能直接就将每个点连接边做矩乘，但是数据范围太大又不能不用矩乘。
注意到边权为 (1)~(9) ，所以可以将每一个点拆成 (9) 个点，若原先每个点为 (i) ，则拆后的点为 ((i-1)*9+n~(1le nle9))， (i) 的主点为 ((i-1)*9+1) ，并将点 ((i-1)*9+n) 和 ((i-1)*9+n+1) 连边长为 (1) 。
然后连长度不为 (1) 的边就很方便了，若连点 (u) 和 (v) 边权为 (k) ，则连接 ((u-1)*9+k) 和 ((v-1)*9+1) ，这样，从 (u) 的主点必须要走 (k-1) 个单位，再走这条边才到的主点，且可以使用矩阵乘法+快速幂。
最后答案即为 (1) 的主点到 (n) 的主点的距离。
(large{ exttt{Code}})
#include<bits/stdc++.h>
using namespace std;
// #define int long long
const int mod=2009;
const int N=10;
int a,b;
char ch;
struct node {
int n,m,s[1010][1010];
inline void Mem() {memset(s,0,sizeof(s));}
inline void Re() {for(int i=1;i<=n;i++) s[i][i]=1;}
inline void print() {for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) printf("%d ",s[i][j]); puts("");}}
node operator*(const node b) {
node sum;
sum.Mem();
sum.n=n;
sum.m=b.m;
for(int i=1;i<=n;i++) for(int j=1;j<=b.m;j++) {for(int k=1;k<=m;k++) sum.s[i][j]=(sum.s[i][j]+s[i][k]*b.s[k][j]); sum.s[i][j]%=mod;}
return sum;
}
} S,A;
inline void Pow(int n) {//矩阵快速幂
while(n) {
if(n&1) S=S*A;
A=A*A;
n>>=1;
}
}
signed main() {
// freopen("in","r",stdin);
scanf("%d%d",&a,&b);
S.n=S.m=a*9;
for(int i=1;i<=a;i++) for(int j=1;j<=8;j++) S.s[(i-1)*9+j][(i-1)*9+j+1]=1;
for(int i=1;i<=a;i++) {
getchar();//防止scanf读入偏差
for(int j=1;j<=a;j++) {
scanf("%c",&ch);
if(ch!='0') S.s[(i-1)*9+ch-'0'][(j-1)*9+1]=1;
}
}
A=S;
Pow(b-1);
//S.print();
printf("%d",S.s[1][(a-1)*9+1]);
return 0;
}