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
#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
int n,k,licznik=1;
char tab[3002][3002];
int vis[3002][3002];
long long suma=0,m=1000000007,po_dwa=0,dwojki=0;
vector<pair<int, int> > kol;
long long il[4], wychodzace_dwojki[5], wspolne_dwojki[5],policz=0;//1-pojedyncz, 2-podwojne, 3-potrojne, 4- poczworne	
void bfs(int i,int j)
{
  int dwojki[5]={0};//1-pojedyncz, 2-podwojne, 3-potrojne, 4- poczworne	
  int ile_wychodzacych=0;
  //cout <<i <<" "<<j <<endl;
  map < pair<int,int> ,int > odl;
  map < pair<int,int> ,pair<int,int>  > oj;
  queue<int> kolx,koly;
  kolx.push(i);
  koly.push(j); 
  odl[make_pair(i,j)] = 0; 
  while(!kolx.empty())
  {
  int i=kolx.front();  kolx.pop();                  
  int j=koly.front(); koly.pop();
  if(tab[i-1][j]=='.' && oj[make_pair(i-1,j)] != make_pair(i,j) && vis[i-1][j] >= 0) 
                      {	  
					  	  
                      oj[make_pair(i-1,j)] =make_pair(i,j); 
                      int o = odl[make_pair(i,j)]; 
                      if(o==0) {ile_wychodzacych++;vis[i-1][j]++;}
					  odl[make_pair(i-1,j)] = o + 1;   
					  il[o+1]++;  
						if(o < k-2) 	{                                           
						  kolx.push(i-1);
						  koly.push(j);
						}	                                               
                      }                  
  if(tab[i+1][j]=='.'  && oj[make_pair(i+1,j)] != make_pair(i,j) && vis[i+1][j] >= 0) 
                      {
					  	
                      oj[make_pair(i+1,j)] =make_pair(i,j);  
                      int o = odl[make_pair(i,j)]; 
                      if(o==0) {ile_wychodzacych++;vis[i+1][j]++;}
					  odl[make_pair(i+1,j)] = o + 1;   
					  il[o+1]++;  
						if(o < k-2) 	{                                                
                      kolx.push(i+1);
                      koly.push(j);   }                                      
                      } 
  if(tab[i][j-1]=='.'  && oj[make_pair(i,j-1)] != make_pair(i,j) && vis[i][j-1] >= 0) 
                      {
                      	
                      oj[make_pair(i,j-1)] =make_pair(i,j); 
                      int o = odl[make_pair(i,j)]; 
                      if(o==0) {ile_wychodzacych++;vis[i][j-1]++;}
					  odl[make_pair(i,j-1)] = o + 1;   
					  il[o+1]++;  
						if(o < k-2) 	{                                                  
                      kolx.push(i);
                      koly.push(j-1); }                                               
                      } 
  if(tab[i][j+1]=='.'  && oj[make_pair(i,j+1)] != make_pair(i,j) && vis[i][j+1] >= 0) 
                      {
                      	
                      oj[make_pair(i,j+1)] =make_pair(i,j); 
                      int o = odl[make_pair(i,j)]; 
                      if(o==0) {ile_wychodzacych++;vis[i][j+1]++;}
					  odl[make_pair(i,j+1)] = o + 1;   
					  il[o+1]++;  
						if(o < k-2) 	{                                                   
                      kolx.push(i);
                      koly.push(j+1); }   
                                       
                      } 
  } 
   wychodzace_dwojki[ile_wychodzacych]++; 
}
  int policz_wspolne(int i,int j)
{
	int ile = 0;
  if(tab[i-1][j]=='.' && tab[i][j+1]=='.' && tab[i-1][j+1]=='.') 
                      {	  
					    ile++;                                          
                      }                  
  if(tab[i][j+1]=='.' && tab[i+1][j]=='.' && tab[i+1][j+1]=='.'  ) 
                      {
                          ile++;             
                      } 
  if(tab[i+1][j]=='.' && tab[i][j-1]=='.'  && tab[i+1][j-1]=='.') 
                      {
                          ile++;                      
                      } 
  if( tab[i][j-1]=='.' && tab[i-1][j]=='.' && tab[i-1][j-1]=='.' ) 
                      {
                           ile++;              
                      } 
   return ile; 
  } 
                  
 long long k_nad_n(int k,int n){
	 long long wyn = 1;
	 for(int i = n - k + 1 ; i <= n; ++i) {wyn *= i;}
	 for(int i = 2; i <= k ; ++i) wyn /= i;
	 return wyn%m;
 }
///////////////////////////////////////
int main()
{
int i, j;	
scanf("%d%d",&n,&k);
for(i=1;i<n+1;++i)
			scanf("%s",&tab[i][1]);	

for(i=0;i<n+2;++i)
   tab[i][0] = tab[i][n+1] = '#';
for(j=0;j<n+2;++j) 
		tab[0][j] = tab[n+1][j] ='#';		
/*
cout <<endl;
for(i=0;i<n+2;++i)
	{for(j=0;j<n+2;++j) cout <<tab[i][j]; 
	cout <<endl;}
 */		
for(i=1;i<n+1;++i)
	for(j=1;j<n+1;++j) {
		if(tab[i][j] == '#'){
			if(tab[i+1][j]=='.' && vis[i+1][j] ==0){
				kol.push_back(make_pair(i+1,j));
				vis[i+1][j]=-1;	
			}
			if(tab[i-1][j]=='.' && vis[i-1][j] ==0){
				kol.push_back(make_pair(i-1,j));
				vis[i-1][j]=-1;	
			}
			if(tab[i][j+1]=='.' && vis[i][j+1] ==0){
				kol.push_back(make_pair(i,j+1));
				vis[i][j+1]=-1;	
			}
			if(tab[i][j-1]=='.' && vis[i][j-1] ==0){
				kol.push_back(make_pair(i,j-1));
				vis[i][j-1]=-1;	
			}
		}
}  
il[0]=kol.size();         
  //for(i = 0; i < kol.size();++i) vis[kol[i].first][kol[i].second]=0;
  for(i = 0; i < kol.size();++i) {  bfs(kol[i].first,kol[i].second);licznik++; }
  //for(j = 0; j < 4;++j) cout << il[j]<<" ";	cout << endl;}
  for(i=1;i<n+1;++i)
	for(j=1;j<n+1;++j) if(vis[i][j]>0) {wspolne_dwojki[vis[i][j]]++,dwojki++;}
    //for(i = 0; i < kol.size();++i) cout <<      kol[i].first<<" "<<kol[i].second<<endl;
	//for(i = 0; i < 4;++i) cout << il[i]<<" ";	cout << endl; 
	if(k==1)
	{
		suma = kol.size() ;
		//printf("%lld\n",suma);
	}
	if(k==2)
	{	
		suma += il[1];//2
		suma += (k_nad_n(2,kol.size() ) )%m;//1 + 1
		//printf("%lld\n",suma);
	}
	if(k==3){	
		suma += (il[2])%m ;//3 
		//cout << (il[2])%m << endl;
		suma += ((il[1])*(kol.size() - 1)-wspolne_dwojki[2] - wspolne_dwojki[3]*3 - wspolne_dwojki[4]*6)%m ;//2 + 1
		//cout << ((il[1])*(kol.size() - 1)-wspolne_dwojki[2] - wspolne_dwojki[3]*3 - wspolne_dwojki[4]*6)%m <<endl;
		suma += (k_nad_n(3,kol.size() ))%m; //1 + 1 +1
		//cout << (k_nad_n(3,kol.size() ))%m << endl;
		//printf("%lld\n",suma);
	}
	if(k==4){
		suma += il[3];// 4 -ilosc takich, z ktorych wychodza pod katem prostym 2 
		for(i = 0; i < kol.size();++i) policz += policz_wspolne(kol[i].first,kol[i].second);
		suma -= policz;
		po_dwa =  (wychodzace_dwojki[3]*3*(il[1] - 3) + wychodzace_dwojki[2]*2*(il[1] - 2) + wychodzace_dwojki[1]*1*(il [1] - 1))%m;//2 + 2
		po_dwa = (po_dwa - 2*wspolne_dwojki[2] - 3*wspolne_dwojki[3] - 4*wspolne_dwojki[4])%m;	
		suma += po_dwa;
		suma += ((il[1] )*k_nad_n(2,kol.size()-1 ) - wspolne_dwojki[2] - wspolne_dwojki[3]*2 - wspolne_dwojki[4]*3)%m;//2 + 1 + 1
		suma += (il[2] * (kol.size() -1))%m;//3 + 1 
		suma += (k_nad_n(4,kol.size() ))%m;//1 + 1 + 1 + 1
		j++;
		//printf("%lld\n",suma);
	}
	printf("%lld\n",suma%m);

return 0;
}