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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <cassert>

#include <vector>

typedef unsigned long long int llu;

static const int MAX_N = 3000;
static const llu MODULO_BY = 1000 * 1000 * 1000 + 7;

bool matrix[MAX_N][MAX_N];
bool ones[MAX_N][MAX_N];
uint8_t twos[MAX_N][MAX_N];

llu ones_count;
llu twos_sum;

int n, k;

llu solve_one();
llu solve_two();
llu solve_three();
llu solve_four();

inline llu safe_mul(llu a, llu b) {
	return (a * b) % MODULO_BY;
}

llu safe_mul_div(std::vector<llu> noms, std::vector<llu> denoms) {
	llu ret = 1;
	for (llu nom : noms) {
		int i = 0;
		while (i < denoms.size()) {
			const llu denom = denoms[i];
			if (nom % denom == 0) {
				nom /= denom;
				denoms.erase(denoms.begin() + i);
			}
			else {
				i++;
			}
		}
		ret = safe_mul(ret, nom);
	}

	assert(denoms.empty());
	return ret;
}

llu safe_count_tuples(llu n, llu k) {
	std::vector<llu> noms, denoms;
	for (llu i = 0; i < k; i++) {
		noms.push_back(n - i);
		denoms.push_back(k - i);
	}

	return safe_mul_div(std::move(noms), std::move(denoms));
}

void read_data() {
	scanf("%d %d", &n, &k);

	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			int c = getchar();
			while (c != '#' && c != '.') {
				c = getchar();
			}
			matrix[y][x] = (c == '#');
		}
	}
}

inline bool is_ones(int x, int y) {
	if (x < 0 || y < 0 || x >= n || y >= n) {
		return false;
	}
	return ones[y][x];
}

inline uint8_t get_twos(int x, int y) {
	if (x < 0 || y < 0 || x >= n || y >= n) {
		return 0;
	}
	return twos[y][x];
}

llu solve_one() {
	// That's easy!
	return ones_count;
}

llu solve_two() {
	// Two cases:
	// 1. Two tiles lie next to already placed tiles
	// 2. One of the tiles is a "two", second is a "one"
	return (safe_count_tuples(ones_count, 2) + twos_sum) % MODULO_BY;
}

llu solve_three() {
	// Four cases this time:
	// 1. All three tiles are "ones"
	llu ret = safe_count_tuples(ones_count, 3);

	// 2. One tile is a "two", with two "ones" adjacent
	// 3. One tile is a "two", second is a "one", third is also a "one" but not adjacent
	// 4. One tile is a "two", second is a "one", third is something else (but adjacent)
	llu count = 0;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			// Case 2
			count += (llu)(twos[y][x] * (twos[y][x] - 1) / 2);

			// Case 3
			count += (llu)(twos[y][x] * (ones_count - twos[y][x]));

			// Case 4
			const uint8_t unclassified
				= ((x <= 0 || (!ones[y][x - 1] && twos[y][x - 1] == 0)) ? 1 : 0)
				+ ((x >= n - 1 || (!ones[y][x + 1] && twos[y][x + 1] == 0)) ? 1 : 0)
				+ ((y <= 0 || (!ones[y - 1][x] && twos[y - 1][x] == 0)) ? 1 : 0)
				+ ((y >= n - 1 || (!ones[y + 1][x] && twos[y + 1][x] == 0)) ? 1 : 0);
			count += (llu)(twos[y][x] * unclassified);
			count %= MODULO_BY;
		}
	}
	return (ret + count) % MODULO_BY;
}

llu solve_four() {
	// 1: All four tiles are "ones"
	llu ret = safe_count_tuples(ones_count, 4);

	// 2: One tile is a "two", three "ones" are adjacent
	// 3:                      two "ones" are adjacent, last tile is something else, but adjacent
	// 4:                                               last tile is a non-adjacent "one"
	// 5:                      one "one" is adjacent, two tiles are something else, but adjacent
	// 6:                                             one tile is an adjacent "one", last is adjacent something-else
	// 7:                                             two tiles are something-else
	return 0;
}

llu count() {
	// Place "ones"
	llu count = 0;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			if (matrix[y][x]) {
				continue;
			}
			ones[y][x]
				= (x > 0 && matrix[y][x - 1])
				|| (x < n - 1 && matrix[y][x + 1])
				|| (y > 0 && matrix[y - 1][x])
				|| (y < n - 1 && matrix[y + 1][x]);
			if (ones[y][x]) {
				count++;
			}
		}
	}
	ones_count = count;

	// Place "twos"
	count = 0;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			if (matrix[y][x] || ones[y][x]) {
				continue;
			}
			twos[y][x]
				= ((x > 0 && ones[y][x - 1]) ? 1 : 0)
				+ ((x < n - 1 && ones[y][x + 1]) ? 1 : 0)
				+ ((y > 0 && ones[y - 1][x]) ? 1 : 0)
				+ ((y < n - 1 && ones[y + 1][x]) ? 1 : 0);
			count += (llu)twos[y][x];
		}
	}
	twos_sum = count;

	if (k == 1) {
		return solve_one();
	}
	else if (k == 2) {
		return solve_two();
	}
	else if (k == 3) {
		return solve_three();
	}
	/*else if (k == 4) {
		return solve_four();
	}*/

	puts("MACHINE BROKE");
	return 0;
}

int main() {
	read_data();
	const llu result = count();
	printf("%llu\n", result);

	return 0;
}