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
#include <bits/stdc++.h>
using namespace std;

#define For(a, b, i) for(int i = a; i < b; ++i)
#define Dfor(a, b, i) for(int i = a; i >= b; --i)
#define ll long long
#define maxn 4000
#define mod 1000000007

int n, k;
char t[maxn][maxn];

ll newton[2500010][5];
bool odw[maxn][maxn];
ll x1 = 0, x2 = 0, x3 = 0, sx2 = 0;

int a[maxn][maxn];

void wczytaj()
{
	cin >> n >> k;
	For(0, n, i) cin >> t[i];
}

void build_newton()
{
	For(0, 250010, i)
		For(0, 5, j)
		{
			if(!j) newton[i][j] = 1;
			else if(i == j) newton[i][j] = 1;
			else if(i > j) newton[i][j] = (newton[i - 1][j] + newton[i - 1][j - 1])%mod;
		}
}

void prepare()
{
	Dfor(n, 0, i)
		Dfor(n, 0, j)
			if(j && i) t[i][j] = t[i - 1][j - 1];
			else t[i][j] = 0;
	
	For(1, n + 1, i)
		For(1, n + 1, j)
			if(t[i][j] == '.')
				if(t[i][j + 1] == '#' || t[i][j - 1] == '#' || t[i + 1][j] == '#' || t[i - 1][j] == '#') odw[i][j] = 1, x1++;
}

void build()
{
	For(1, n + 1, i)
		For(1, n + 1, j)
			if(!odw[i][j] && t[i][j] == '.')
			{
				if(t[i][j+1] == '.' && odw[i][j+1]) a[i][j]++;
				if(t[i][j-1] == '.' && odw[i][j-1]) a[i][j]++;
                if(t[i+1][j] == '.' && odw[i+1][j]) a[i][j]++;
				if(t[i-1][j] == '.' && odw[i-1][j]) a[i][j]++;
                
                
                
				if(x2 < a[i][j]) x3 = x2, x2 = a[i][j];
				else if(x3 < a[i][j]) x3 = a[i][j];
				
				sx2 += a[i][j];
			}
}

int main()
{
	ios_base::sync_with_stdio();
	cin.tie(0);
	
	wczytaj();
	
	prepare();
	
	build();
	
	build_newton();
	
    if(k == 1) cout << x1 << "\n", exit(0);
    
    else if(k==2) cout << ((x1 * (x1 - 1))/2 + sx2)%mod << "\n", exit(0);
	
    else if(k==3) cout << ((newton[x1][3] + x2 * (x1 - 1))/2 + ((x1 - 2) * (((x2 * (x2 - 1))/2)%mod)%mod))%mod << "\n", exit(0);
    
    else if(k == 4) cout << (newton[x1][4] + (x2 * x3)%mod + ((x2 * (x1-2))%mod + mod)%mod  +  ((x3*(x1-2))%mod + mod)%mod)%mod << "\n", exit(0);
}