1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;
const int mx=3e3+3, mod=1e9+7;

int n, k;
long long wynik[5];
long long dodane[5];
int tab[mx][mx], tt[mx][mx];
int dx[4]= {1, -1, 0, 0};
int dy[4]= {0, 0, 1, -1};
set <vector <int> > S;

void wczyt(){
	scanf("%d %d ",&n,&k);
	
	for(int i=1; i<=n; i++){	
		for(int j=1; j<=n; j++){
			char zn;
			scanf(" %c",&zn);
			if(zn=='#')
				tab[i][j]=1;
		}
	}
}
long long liczenie(int x){
	long long wyn=((wynik[x-1]*(wynik[x-1]-1LL))/2LL)%mod;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			tt[i][j]=tab[i][j];
			if(tab[i][j]==0){
				bool zm=false;
				for(int s=0; s<4; s++){
					if(tab[i+dx[s]][j+dy[s]]==1)
						zm=true;
				}
				if(zm==true){
					tt[i][j]=1;
				}
			}
			//printf("%d",tt[i][j]);
		}
		//puts(" ");
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			tab[i][j]=tt[i][j];
			if(tt[i][j]==0){
				//printf("%d %d\n",i,j);
				for(int s=0; s<4; s++){
					//printf(">>%d %d\n",i+dx[s], j+dy[s]);
					if(tt[i+dx[s]][j+dy[s]]==1){
						//puts("tak");
						wyn=(wyn+1LL)%mod;
					}
				}
			}
		}
	}
	
	return wyn;
}
void fun(vector <int> vec){
	//puts("TUTAJ");
	if(!vec.empty() && vec.size()==k){
		sort(vec.begin(), vec.end());
		S.insert(vec);
		return;
	}
	//puts("TUTAJ");
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			bool zm=false;
			//printf("%d",tab[i][j]);
			if(tab[i][j]==0){
				for(int s=0; s<4; s++){
					if(tab[i+dx[s]][j+dy[s]]==1)
						zm=true;
				}
				if(zm==true){
					vec.push_back((i-1)*n+j);
					tab[i][j]=1;
					fun(vec);
					tab[i][j]=0;
					vec.pop_back();
				}
			}
		}
	}
}

int main(){
	wczyt();
	if(k>2){
		vector <int> vec;
		fun(vec);
		printf("%d\n",((int)S.size())%mod);
	}
	if(k<=2){
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				if(tab[i][j]==0){
					bool zm=false;
					for(int s=0; s<4; s++){
						if(tab[i+dx[s]][j+dy[s]]==1)
							zm=true;
					}
					if(zm==true)
						wynik[1]=(wynik[1]+1LL)%mod;
				}
			}
		}
		dodane[1]=wynik[1];
		for(int i=2; i<=k; i++)
			wynik[i]=liczenie(i);
		
		printf("%lld\n",wynik[k]);
	}
	return 0;
}