换了种做法，第二个样例过不去，并且调试不出来（大的样例没法调，小的不出错）。由于写法和题解略有不同，找不出错误。

#include<iostream>
#include<cstdio>
using namespace std;
const int mod=2009,maxn=150;
int N,T,N2,a[maxn][maxn],b[maxn][maxn],ls[maxn][maxn];
void calc(int _N,int _M,int _P,int _a[maxn][maxn],int _b[maxn][maxn],int _c[maxn][maxn]){
    for(int i=1;i<=_N;i++){
        for(int j=1;j<=_P;j++){
            ls[i][j]=0;
            for(int k=1;k<=_M;k++){
                ls[i][j]+=_a[i][k]*_b[k][j];
            }
            ls[i][j]%=mod;
        }
    }
    for(int i=1;i<=_N;i++){
        for(int j=1;j<=_P;j++){
            _c[i][j]=ls[i][j];
        }
    }
}
void qsm(int t){
    for(;t;t>>=1){
        if(t&1)  calc(N2,N2,N2,b,a,b);
        calc(N2,N2,N2,a,a,a);
    }
}
int main(){
    scanf("%d%d",&N,&T);N2=(N+1)*10;
    for(int i=1;i<=N;i++){//a little bigger
    	for(int j=0;j<=9;j++)  a[i*10+j][i*10+j+1]=1;
    }
    for(int i=1;i<=N;i++){
        char c=getchar();
        while(c<'0'||c>'9')  c=getchar();
        for(int j=1;'0'<=c&&c<='9';j++){
            if(c-='0')  a[i*10+c-1][j*10]=1;
//            printf("tag %d %d\n",i*10+c-1,j*10);
            c=getchar();
        }
    }
    for(int i=1;i<=N2;i++)  b[i][i]=1;
    qsm(T);
    printf("%d\n",b[10][N*10]);
    return 0;
}