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
/*
 * CAR
 * Autor: Szymon Tur
 */

#include <iostream>

#define MOD 1000000007

using namespace std;

int n, k, ones = 0;
int ** plansza;
int ** s;

long long binomial(int x, int y)
{
	if (y>x) return 0;
	if (y == 0 || y == x) return 1;
	long long q = 1;
	for (int i = x;i >= x - y + 1;i--) q *= i;
	for (int i = 2;i <= y;i++) q /= i;
	return q;
}
void setNumbers(int g)
{
	for (int i = 0;i<n;i++)
		for (int j = 0;j<n;j++)
		{
			if (plansza[i][j] < g && i + 1<n && plansza[i + 1][j] == g + 1) { plansza[i][j] = g; if (g == k) ++ones; continue; }
			if (plansza[i][j] < g && i - 1 >= 0 && plansza[i - 1][j] == g + 1) { plansza[i][j] = g; if (g == k) ++ones; continue; }
			if (plansza[i][j] < g && j + 1<n && plansza[i][j + 1] == g + 1) { plansza[i][j] = g; if (g == k) ++ones; continue; }
			if (plansza[i][j] < g && j - 1 >= 0 && plansza[i][j - 1] == g + 1) { plansza[i][j] = g; if (g == k) ++ones; continue; }
		}
}

int main()
{
	cin >> n >> k;
	plansza = new int * [n];
	for (int i = 0;i<n;i++) plansza[i] = new int [n];
	s = new int * [k + 1];
	for (int i = 0;i <= k;i++) s[i] = new int [k + 1];
	for (int i = 0;i <= k;i++)
		for (int j = 0;j <= k;j++) s[i][j] = 0;
	char _x;
	for (int i = 0;i<n;i++)
		for (int j = 0;j<n;j++)
		{
			cin >> _x;
			if (_x == '.')
				plansza[i][j] = 0;
			else
				plansza[i][j] = k + 1;
		}
	for (int i = k;i>0;i--) setNumbers(i);
	for (int i = 0;i<n;i++)
		for (int j = 0;j<n;j++)
		{
			if (i + 1<n && plansza[i + 1][j] - plansza[i][j] == 1 && plansza[i+1][j]<=k) ++s[plansza[i + 1][j]][plansza[i][j]];
			if (i + 1<n && plansza[i + 1][j] - plansza[i][j] == 0 && plansza[i + 1][j] <= k) ++s[plansza[i + 1][j]][plansza[i][j]];
			if (j + 1<n && plansza[i][j + 1] - plansza[i][j] == 1 && plansza[i][j+1] <= k) ++s[plansza[i][j + 1]][plansza[i][j]];
			if (j + 1<n && plansza[i][j + 1] - plansza[i][j] == 0 && plansza[i][j+1] <= k) ++s[plansza[i][j + 1]][plansza[i][j]];
			if (i + 1<n && plansza[i + 1][j] - plansza[i][j] == -1 && plansza[i][j] <= k) ++s[plansza[i][j]][plansza[i + 1][j]];
			if (j + 1<n && plansza[i][j + 1] - plansza[i][j] == -1 && plansza[i][j] <= k) ++s[plansza[i][j]][plansza[i][j + 1]];
		}
	long long sum;
	sum = binomial(ones, k) % MOD;
	if (k>1) sum += (binomial(ones-1, k - 2)%MOD)*(s[k][k - 1]) % MOD;
	if (k>2) sum += (binomial(ones-1, k - 3)%MOD)*(s[k - 1][k - 1] + s[k - 1][k - 2]) % MOD;
	if (k>3) sum += ((binomial(ones-1, k - 4)%MOD)*((binomial(s[k - 1][k - 1], 2) + s[k - 1][k - 2] + s[k - 2][k - 2] + s[k - 2][k - 3])%MOD) % MOD) + (binomial(s[k][k-1],2)%MOD);
	sum %= MOD;
	cout << sum;
	return 0;
}