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
#include <cstdio>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define INT(x) int x; scanf("%d", &x)

const int DX[4] = {0, 1, 0, -1}, DY[4] = {1, 0, -1, 0};
int n, k;
char a[3000][3001];
int connect[3000][3000];
int cx[3000], cy[3000];
int numcon;
int res;

void go(int s) {
	if (!k) {
		++res;
		if (res == 1000000007) res = 0;
		return;
	}
	int nn = numcon;
	FOR(i,s,nn) {
		int x = cx[i], y = cy[i];
		a[x][y] = '*';
		REP(kk,4) {
			int xx = x + DX[kk];
			int yy = y + DY[kk];
			if (xx >= 0 && xx < n && yy >= 0 && yy < n && a[xx][yy] == '.' && ++connect[xx][yy] == 1) {
				cx[numcon] = xx;
				cy[numcon] = yy;
				++numcon;
			}
		}
		--k;
		go(i + 1);
		++k;
		REP(kk,4) {
			int xx = x + DX[kk];
			int yy = y + DY[kk];
			if (xx >= 0 && xx < n && yy >= 0 && yy < n && a[xx][yy] == '.' && !--connect[xx][yy]) --numcon;
		}
		a[x][y] = '.';
	}
}

int main() {
	INT(n1);
	INT(k1);
	n = n1;
	k = k1;
	REP(i,n) scanf("%s", &a[i]);
	REP(i,n) REP(j,n) if (a[i][j] == '#') REP(kk,4) {
		int ii = i + DX[kk];
		int jj = j + DY[kk];
		if (ii >= 0 && ii < n && jj >= 0 && jj < n && a[ii][jj] == '.' && ++connect[ii][jj] == 1) {
			cx[numcon] = ii;
			cy[numcon] = jj;
			++numcon;
		}
	}
	go(0);
	printf("%d\n", res);
}