#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,t;
struct jz{int a[105][105];};
inline jz operator *(jz a,jz b){
	jz c;
	memset(c.a,0,sizeof c.a);
	for(int i=1;i<=100;i++)
		for(int j=1;j<=100;j++)
			for(int l=1;l<=100;l++)
				c.a[i][l]+=a.a[i][j]*b.a[j][l],c.a[i][l]%=2009;
	return c;
}
jz mp,a0;
char a[15][15];
jz po(jz a,int b){
	if(b==0)return a0;
	if(b==1)return a;
	jz d=po(a,b>>1);
	return d*d*po(a,b&1);
}
int ans;
signed main(){
	for(int i=1;i<=100;i++)a0.a[i][i]=1;
	cin>>n>>t;
	for(int i=1;i<=n;i++)
		for(int j=2;j<=10;j++)
			mp.a[(i-1)*10+j][(i-1)*10+j-1]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			if(a[i][j]-'0')mp.a[(i-1)*10+1][(j-1)*10+a[i][j]-'0'+1]=1;
		}
	jz s=po(mp,t);
	cout<<s.a[1][(n-1)*10+1]%2009;
}