#include<iostream>#include<string.h>using namespace std;#define K_MAX 51#define N_MAX 22#define clr(a) memset(a, 0, sizeof(a))int x[K_MAX][N_MAX * N_MAX], y[K_MAX][N_MAX * N_MAX], flag[N_MAX][N_MAX];int p[K_MAX]; int map[N_MAX][N_MAX];int N, K;int rx[4]={0, -1, 0, 1}; int ry[4]={-1, 0, 1, 0}; int num[N_MAX][N_MAX][31];int input(){ if(cin>>N>>K) { for(int i=1; i<=N; i++) { char temp[N]; cin>>temp; for(int j=1; j<=N; j++) { if(temp[j-1] == '1') { map[i][j]=1; } else { map[i][j]=0; } } } return 1; } else { return 0; }}void my_init(){ x[0][0]=1; y[0][0]=1; clr(num); num[1][1][0]=1; p[0]=1; for(int i=0; i<=N+1; i++) { map[0][i]=1; map[i][0]=1; map[N+1][i]=1; map[i][N+1]=1; }}void my_plus(int *a, int *b){ int temp; for(int i=30; i>=0; i--) { if( b[i] != 0 || a[i] != 0) { temp=i; break; } } int ca1, ca2; ca1=0; for(int i=0; i<=temp; i++) { ca2=(a[i]+b[i]+ca1) / 10; a[i]=(a[i]+b[i]+ca1) % 10; ca1=ca2; } if(ca1!=0) { a[temp+1]=1; }}void DP(){ for(int t=1; t<=K; t++) { clr(flag); p[t]=0; for(int i=0; i<p[t-1]; i++) { int xtemp=x[t-1][i]; int ytemp=y[t-1][i]; for(int j=0; j<4; j++) { if(!map[xtemp+rx[j]][ytemp+ry[j]]) { my_plus( num[xtemp+rx[j]][ytemp+ry[j]], num[xtemp][ytemp] ); if(!flag[xtemp+rx[j]][ytemp+ry[j]]) { flag[xtemp+rx[j]][ytemp+ry[j]]=1; x[t][p[t]]=xtemp + rx[j]; y[t][p[t]++]=ytemp + ry[j]; } } } clr(num[xtemp][ytemp]); } }}void my_out(){ int p=0; for(int i=30; i>=0; i--) { if(num[N][N][i]!=0) { p=i; break; } } for(int i=p; i>=0; i--) { cout<<num[N][N][i]; } cout<<endl;}int main(){ while(input()) { my_init(); DP(); my_out(); } return 0;}
