先思考\(C_{i,j}\)要么只有0和1两种值的情况，那么这种情况就是求矩阵\(C^k\)中的\(C_{1,n}\)的值。
证明：令矩阵\(G=C^2=\sum\limits_{k=1}^nC(i,k)*C(k,j)\)，即当\(C(i,k)\)和\(C(k,j)\)都为1时，才有\(C(i,k)*C(k,j)\)才为1，表示\(i->k->j\)的路径，而\(G(i,j)\)即计算了枚举了所有中间点\(k\)的合法路径数量。所以\(G(i,j)\)表示在\(t=2\)时\(i->j\)不同路径的数量
令矩阵\(M=C^3=G*C=\sum\limits_{k=1}^nG(i,k)*C(k,j)\)，表示\(i->k\)经过两条边有\(G(i,k)\)个数不同路径，而\(k->j\)经过一条边有\(C(k,j)\)条路径，乘起来即\(i->k->j\)经过三条边的合法路径数量，再枚举所有的k，即\(M(i,j)\)表示\(i->j\)经过三条边的合法路径数量
以此类推
那么考虑\(C_{i,j}=0\)~\(9\)的情况，我们可以把一个点拆成九个点。
eg:我们将\(A_1\)拆成\(A_{1,1}\)~\(A_{1,9}\)，然后连接\(A_{1,1}\)与\(A_{1,2}\)、\(A_{1,2}\)与\(A_{1,3}\)......\(A_{1,8}\)与\(A_{1,9}\)，使他们边权为1。
\(u->v\)边权为\(k\)就与就将\(A_{u,k}\)与\(A_{v,1}\)连一条边权为1的边。
再将他们放到邻接矩阵\(B\)内，输出\(B_{(1,1),(n,1)}\)
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=110,mod=2009;
ll n,n1,k,zh,gs,zuo=1,you=1;
char sr;
struct jgt
{
ll a[N][N];
}ans,mi;
jgt operator * (const jgt t1,const jgt t2)
{
jgt t={0};
for(ll i=1;i<=n1;i++)
for(ll j=1;j<=n1;j++)
for(ll k=1;k<=n1;k++)
t.a[i][j]=(t.a[i][j]+(t1.a[i][k]*t2.a[k][j])%mod)%mod;
return t;
}
int main()
{
scanf("%lld %lld",&n,&k);
n1=n*9;
for(ll i=1;i<=n;i++)
for(ll j=1;j<=8;j++)
mi.a[(i-1)*9+j][(i-1)*9+j+1]=1;
while(zuo<=n)
{
scanf("%c",&sr);
if(sr<'0'||sr>'9') continue;
if(sr>'0') mi.a[(zuo-1)*9+sr-'0'][(you-1)*9+1]=1;
you++;
if(you>n) you-=n,zuo++;
}
for(ll i=1;i<=n1;i++) ans.a[i][i]=1;
while(k)
{
if(k&1) ans=ans*mi;
mi=mi*mi;
k=k/2;
}
printf("%lld\n",ans.a[1][n1-8]);
return 0;
}