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
#include <algorithm>
#include <vector>
#include <map>
#include <cstdio>
#include <utility>  
const int MAX1 = 25000000;
const int MAX2 = 3001;

using namespace std;

int count(int x[MAX1], int y[MAX1], bool orginal[MAX2][MAX2], int board[MAX2][MAX2], int size,
	int start, int k, int player, int n) {
	if (k == 0) {
		return 1;
	}
	int result = 0;
	for (int i = start; i < size; ++i) {
		bool up = x[i] == 0 || orginal[x[i] - 1][y[i]];
		bool down = x[i] == n - 1 || orginal[x[i] + 1][y[i]];
		bool left = y[i] == 0 || orginal[x[i]][y[i] - 1];
		bool right = y[i] == n - 1 || orginal[x[i]][y[i] + 1];
		if (!orginal[x[i]][y[i]] || (left && right && down && up)) {
			continue;
		}
		orginal[x[i]][y[i]] = false;
		result = (result + count(x, y, orginal, board, size, i + 1, k - 1, player + 1, n)) % 1000000007;
		orginal[x[i]][y[i]] = true;
	}
	return result;
}

int main() {
	int n, k;
	scanf("%d", &n);
	scanf("%d", &k);
	int empty = 0;
	int board[MAX2][MAX2];
	bool orginal[MAX2][MAX2];
	char row[MAX2];
	for (int i = 0; i < n; ++i) {
		scanf("%s", row);
		for (int j = 0; j < n; ++j) {
			if (row[j] == '.') {
				board[i][j] = 0;
				orginal[i][j] = true;
				empty++;
			}
			else {
				board[i][j] = 1;
				orginal[i][j] = false;
			}
		}
	}
	empty--;
	int x[MAX1];
	int y[MAX1];
	int size = 0;
	for (int l = 1; l < k + 1; ++l) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (board[i][j] == l) {
					bool left = i > 0 && board[i - 1][j] == 0;
					if (left) {
						x[size] = i - 1;
						y[size] = j;
						size++;
						if(board[i - 1][j] == 0) board[i - 1][j] = l + 1;
					}
					bool right = i < n - 1 && board[i + 1][j] == 0;
					if (right) {
						x[size] = i + 1;
						y[size] = j;
						size++;
						if(board[i + 1][j] == 0) board[i + 1][j] = l + 1;
					}
					bool down = j > 0 && board[i][j - 1] == 0;
					if (down) {
						x[size] = i;
						y[size] = j - 1;
						size++;
						if (board[i][j - 1] == 0) board[i][j - 1] = l + 1;
					}
					bool up = j < n - 1 && board[i][j + 1] == 0;
					if (up) {
						x[size] = i;
						y[size] = j + 1;
						size++;
						if (board[i][j + 1] == 0) board[i][j + 1] = l + 1;
					}
				}
			}
		}
	}
	int result = count(x, y, orginal, board, size, 0, k, 0, n);
	printf("%d", result);
	return 0;
}