首先学习是学习矩阵乘法在邻接矩阵的应用
ab两点经过k条边的路径数就等于图的邻接矩阵G的k次幂之后G[a,b]的值
但这道题问的是经过长度为k的路径数
考虑到每条边的长度最长只有9，所以我们把一个点拆成9个点，
i1~i9 顺次相连长度为1，i9为出点
对于长度为k的边eij，连边i9-->j(10-k) 长度为1
这样图中的每条边的长度都变成了1，就相当于求k条边的路径数了
const mo=;
var ans,a,b,c:array[..,..] of longint;
d:array[..] of longint;
i,j,k,x,n,m:longint;
ch:char; procedure mul;
var i,j,k:longint;
begin
for i:= to n do
for j:= to n do
begin
ans[i,j]:=;
for k:= to n do
ans[i,j]:=(ans[i,j]+a[i,k]*b[k,j] mod mo) mod mo;
end;
end; procedure quick(x:longint);
var i,j,p,q:longint;
begin
j:=;
while x<> do
begin
inc(j);
d[j]:=x mod ;
x:=x shr ;
end;
fillchar(ans,sizeof(ans),);
for i:= to n do
ans[i,i]:=;
for i:=j downto do
begin
a:=ans;
b:=ans;
mul;
if d[i]= then
begin
a:=ans;
b:=c;
mul;
end;
end;
end; begin
readln(n,m);
for i:= to n do
begin
for j:= to n do
begin
read(ch);
x:=ord(ch)-;
if x<> then
begin
c[i*,j*-x+]:=;
for k:=j*-x+ to j*- do
c[k,k+]:=;
end;
end;
readln;
end;
n:=n*;
quick(m);
writeln(ans[,n]);
end.