#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 1145
using namespace std;
int idd(int pos,int dep){return (pos-1)*10+dep;}
int n,t;
struct matrix{
	int l,h;
	int m[N][N];//底下那个实际没有用
	matrix(int a=100,int b=100){l=n*10,h=n*10,memset(m,0,sizeof(m));}
	void csh(){
		memset(m,0,sizeof(m));
		for(int i=1;i<=n*10;i++)m[i][i]=1;
	}
	matrix operator *(const matrix &a)const{
		matrix ans=matrix(n*10,n*10);
		for(int k=1;k<=n*10;k++)for(int i=1;i<=n*10;i++)for(int j=1;j<=n*10;j++)ans.m[i][j]=(ans.m[i][j]+m[i][k]*a.m[k][j]%2009)%2009;
		return ans;
	}
	matrix operator ^(int b){
		matrix ans=matrix(n*10,n*10),a=matrix(n*10,n*10);ans.csh();
		for(int i=1;i<=n*10;i++)for(int j=1;j<=n*10;j++)a.m[i][j]=m[i][j];
		while(b){
			if(b&1)ans=ans*a;
			a=a*a;
			b>>=1;
		}
		return ans;
	}
};
signed main(){
	scanf("%d%d",&n,&t);
	matrix a=matrix(10*n,10*n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=9;j++)a.m[idd(i,j)][idd(i,j+1)]=1;
		for(int j=1;j<=n;j++){
			int x=0;
			scanf("%1d",&x);
			if(x)a.m[idd(i,x)][idd(j,1)]=1;
		}
	}
	a=a^t;
	printf("%d",a.m[1][n*10-9]%2009);
	return 0;
}