#include <cstdio>#include <cstring>#include <cstdlib>#include <climits>#include <iostream>#include <algorithm>using namespace std;#define P(x,y) ((y-1)*N+x)const int P=2009;const int MAXN=100+2;int N,M,T,G[MAXN][MAXN],a[MAXN][MAXN],t[MAXN][MAXN],tmp[MAXN][MAXN];char S[MAXN];void Matrix_Mul(bool f){    memset(tmp,0,sizeof(tmp));    if(!f){        for(int i=1;i<=M;i++)        for(int j=1;j<=M;j++)        for(int k=1;k<=M;k++)            tmp[i][j]=(tmp[i][j]+a[i][k]*t[k][j])%P;        memcpy(a,tmp,sizeof(tmp));    }    else{        for(int i=1;i<=M;i++)        for(int j=1;j<=M;j++)        for(int k=1;k<=M;k++)            tmp[i][j]=(tmp[i][j]+t[i][k]*t[k][j])%P;        memcpy(t,tmp,sizeof(t));    }}void Quick_Pow(int x){    memcpy(t,G,sizeof(t));    while(x){        if(x&1) Matrix_Mul(0);        Matrix_Mul(1);        x>>=1;    }}int main(){    scanf("%d %d",&N,&T);    M=N*9;    for(int i=1;i<=N;i++)        for(int j=2;j<=9;j++)            G[P(i,j)][P(i,j-1)]=1;    for(int i=1;i<=N;i++)        for(int j=1,x;j<=N;j++){            scanf("%1d",&x);            if(!x) continue;            G[i][P(j,x)]=1;        }    for(int i=1;i<=M;i++) a[i][i]=1;    Quick_Pow(T);    printf("%d\n",a[1][N]);    return 0;}