如果边权只有 0/1 那么不就是一个灰常简单的矩阵快速幂吗！
然鹅边权 $<=9$
所以我们把每个点拆成9个点！
解决~
#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
using namespace std;
const int mod=;
int m,n,t;long long q;
struct matrix{
int a[][];
matrix(){memset(a,,sizeof(a));}
matrix operator * (const matrix &tmp) const{
matrix c;
for(int i=;i<=n;++i)
for(int j=;j<=n;++j)
for(int k=;k<=n;++k)
c.a[i][j]=(c.a[i][j]+a[i][k]*tmp.a[k][j])%mod;
return c;
}
matrix Pow(matrix x,int y){
matrix res;
for(int i=;i<=n;++i) res.a[i][i]=;
for(;y;y>>=,x=x*x)
if(y&) res=res*x;
return res;
}
}st;
int idx(int x,int y){return x+m*y;}//新点编号
int main(){
scanf("%d%d",&m,&t);n=m*;
for(int i=;i<=m;++i){
for(int j=;j<=;++j)
st.a[idx(i,j)][idx(i,j-)]=;//规定idx(i,0)作为原图的点向其他点连边，其他点与该点的边权就转化为连到idx(i,dist-1)上
scanf("%lld",&q);
for(int j=m;j>=;--j,q/=)
if(q%) st.a[i][idx(j,q%-)]=;
}st=st.Pow(st,t);
printf("%d",st.a[][m]);
return ;
}