1. #include <iostream>
2. using namespace std;
3.  
4. typedef int long long ll;
5. char tab[3000][3000];
6. short int mask[3000][3000][9];
7. short int nx[] = {-1, 1, 0, 0};
8. short int ny[] = {0, 0, 1, -1};
9. int n, k;
10. short int p[] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
11. short int pp[] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
12. short int bad[] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
13. const long long int c = 1e9 + 7;
14.  
15. bool if_fits(int x, int y){
16.     if(x >= 0 && x < n && y >= 0 && y < n)
17.         return 1;
18.     else
19.         return 0;
20. }
21. void neigh(int x, int y, char letter){
22.     p[8] = 0;
23.     for(int i = 0; i < 4; i++)
24.     {
25.         if(if_fits((x + nx[i]),(y + ny[i])) && tab[x + nx[i]][y + ny[i]] == letter)
26.         {
27.             p[2 * i] = x + nx[i];
28.             p[2 * i + 1] = y + ny[i];
29.             p[8] += 1;
30.         }else{
31.             p[2 * i] = -1;
32.         }
33.     }
34. }
35. void neigh2(int x, int y, char letter){
36.     pp[8] = 0;
37.     for(int i = 0; i < 4; i++)
38.     {
39.         if(if_fits((x + nx[i]),(y + ny[i])) && tab[x + nx[i]][y + ny[i]] == letter)
40.         {
41.             pp[2 * i] = x + nx[i];
42.             pp[2 * i + 1] = y + ny[i];
43.             pp[8] += 1;
44.         }else{
45.             pp[2 * i] = -1;
46.         }
47.     }
48. }
49. void zero_bad(){
50.     for(int i = 0; i < 16; i++)
51.     {
52.         bad[i] = -1;
53.     }
54. }
55. int check_bad(int x, int y){
56.     int res = 0;
57.     for(int i = 0; i < 8; i++)
58.     {
59.         if(bad[2 * i] != -1)
60.             {
61.                 if(bad[2 * i] == x && bad[2 * i + 1] == y)
62.                     res += 1;
63.             }
64.     }
65.     return res;
66. }
67. void chceck_bad_for_replies(){
68.     for(int i = 0; i < 8; i++)
69.     {
70.         for(int j = i + 1; j < 8; j++)
71.         {
72.             if(bad[2 * i] == bad[2 * j] && bad[2 * i + 1] == bad[2 * j + 1])
73.                 bad[2 * j] = -1;
74.         }
75.     }
76. }
77. int count_bad(){
78.     int res = 0;
79.     for(int i = 0; i < 8; i++)
80.     {
81.         if(bad[2 * i] != -1)
82.             res += 1;
83.     }
84.     return res;
85. }
86.  
87.  
88. int main()
89. {
90.     cin >> n >> k;
91.     for(int i = 0; i < n; i++)
92.     {
93.         for(int j = 0; j < n; j++)
94.         {
95.             cin >> tab[i][j];
96.             for(int l = 0; l < 27; l++)
97.             {
98.                 mask[i][j][l] = 0;
99.             }
100.         }
101.     }//wczytanie
102.    
103.     for(int x = 0; x < n; x++)
104.     {
105.         for(int y = 0; y < n; y++)
106.         {
107.             if(tab[x][y] == '.')
108.             {
109.                 for(int i = 0; i < 4; i++)
110.                 {
111.                     if(if_fits(x + nx[i], y + ny[i]) && tab[x + nx[i]][y + ny[i]] == '#')
112.                     {
113.                         tab[x][y] = 'a';
114.                     }
115.                     else
116.                         mask[x][y][2 * i] = -1;
117.                 }
118.             }
119.         }
120.     }//wpisanie a
121.    
122.     for(int x = 0; x < n; x++)
123.     {
124.         for(int y = 0; y < n; y++)
125.         {
126.             if(tab[x][y] == '.')
127.             {
128.                 for(int i = 0; i < 4; i++)
129.                 {
130.                     if(if_fits(x + nx[i], y + ny[i]) && tab[x + nx[i]][y + ny[i]] == 'a')
131.                     {
132.                         mask[x][y][8] += 1;
133.                         mask[x][y][2 * i] = x + nx[i];
134.                         mask[x][y][2 * i + 1] = y + ny[i];
135.                         tab[x][y] = 'b';
136.                     }
137.                     else
138.                         mask[x][y][2 * i] = -1;
139.                 }
140.             }
141.         }
142.     }//wpisanie b
143.    
144.     for(int x = 0; x < n; x++)
145.     {
146.         for(int y = 0; y < n; y++)
147.         {
148.             if(tab[x][y] == '.')
149.             {
150.                 for(int i = 0; i < 4; i++)
151.                 {
152.                     if(if_fits(x + nx[i], y + ny[i]) && tab[x + nx[i]][y + ny[i]] == 'b')
153.                     {
154.                         mask[x][y][8] += 1;
155.                         mask[x][y][2 * i] = x + nx[i];
156.                         mask[x][y][2 * i + 1] = y + ny[i];
157.                         tab[x][y] = 'c';
158.                     }
159.                     else
160.                         mask[x][y][2 * i] = -1;
161.                 }
162.             }
163.         }
164.     }//wpisanie c
165.    
166.     for(int x = 0; x < n; x++)
167.     {
168.         for(int y = 0; y < n; y++)
169.         {
170.             if(tab[x][y] == '.')
171.             {
172.                 for(int i = 0; i < 4; i++)
173.                 {
174.                     if(if_fits(x + nx[i], y + ny[i]) && tab[x + nx[i]][y + ny[i]] == 'c')
175.                     {
176.                         mask[x][y][8] += 1;
177.                         mask[x][y][2 * i] = x + nx[i];
178.                         mask[x][y][2 * i + 1] = y + ny[i];
179.                         tab[x][y] = 'd';
180.                     }
181.                     else
182.                         mask[x][y][2 * i] = -1;
183.                 }
184.             }
185.         }
186.     }//wpisanie d
187.    
188.     for(int x = 0; x < n; x++)
189.     {
190.         for(int y = 0; y < n; y++)
191.         {
192.             if(tab[x][y] == 'a')
193.             {
194.                 for(int i = 0; i < 4; i++)
195.                 {
196.                     if(if_fits(x + nx[i], y + ny[i]) && tab[x + nx[i]][y + ny[i]] == 'b')
197.                     {
198.                         mask[x][y][8] += 1;
199.                         mask[x][y][2 * i] = x + nx[i];
200.                         mask[x][y][2 * i + 1] = y + ny[i];
201.                     }
202.                     else
203.                         mask[x][y][2 * i] = -1;
204.                 }
205.             }
206.         }
207.     }//poprawienie maski dla a
208.    
209.     long long int res_a = 0;
210.     for(int x = 0; x < n; x++)
211.     {
212.         for(int y = 0; y < n; y++)
213.         {
214.             if(tab[x][y] == 'a')
215.                 res_a += 1;
216.         }
217.     }//res_a
218.  
219.     for(int i = 0; i < n; i++)
220.     {
221.         for(int j = 0; j < n; j++)
222.         {
223.             cout << tab[i][j] << " ";
224.         }
225.         cout << endl;
226.     }
227.     for(int i = 0; i < n; i++)
228.     {
229.         for(int j = 0; j < n; j++)
230.         {
231.             for(int l = 0; l < 9; l++)
232.             {
233.                 cout << mask[i][j][l] << " ";
234.             }
235.             cout<<endl;
236.         }
237.         cout<<endl;
238.     }
239. if(k == 4)
240.     {
241.         long long int tp;
242.         long long int res_d = (((((((res_a % c) * ((res_a - 1) % c)) % c) * ((res_a - 2) % c)) % c) * ((res_a - 3) % c)) % c) * 41666667; // a-a-a-a
243.         res_d = res_d % c;
244.        
245.         cout << res_d << " ";
246.        
247.         for(int x = 0; x < n; x++)
248.         {
249.             for(int y = 0; y < n; y++)
250.             {
251.                 if(tab[x][y] == 'd')
252.                 {
253.                     for(int i = 0; i < 4; i++)
254.                     {
255.                         if(mask[x][y][2 * i] != -1)
256.                         {
257.                             for(int j = 0; j < 4; j++)
258.                             {
259.                                 if(mask[mask[x][y][2 * i]][mask[x][y][2 * i + 1]][2 * j] != -1)
260.                                 {
261.                                     res_d += (ll)mask [mask[mask[x][y][2 * i]][mask[x][y][2 * i + 1]][2 * j]] [mask[mask[x][y][2 * i]][mask[x][y][2 * i + 1]][2 * j + 1]] [8];
262.                                     res_d = res_d % c;
263.                                     cout << mask [mask[mask[x][y][2 * i]][mask[x][y][2 * i + 1]][2 * j]] [mask[mask[x][y][2 * i]][mask[x][y][2 * i + 1]][2 * j + 1]] [8] << "|";
264.                                 }
265.                             }
266.                         }
267.                     }
268.                    
269.                 }
270.             }
271.         }//a-b-c-d
272.        
273.         cout << res_d << " ";
274.        
275.         for(int x = 0; x < n; x++)
276.         {
277.             for(int y = 0; y < n; y++)
278.             {
279.                 tp = 0;
280.                 if(tab[x][y] == 'b')
281.                 {
282.                     res_d += (ll)(mask[x][y][8] * (mask[x][y][8] - 1) * (mask[x][y][8] - 2) / 6);
283.                     tp = max(0ll,res_a - (ll)mask[x][y][8]);
284.                     res_d += tp * (ll)(mask[x][y][8] * (mask[x][y][8] - 1) / 2);
285.                     res_d = res_d % c;
286.                     res_d += tp * (tp - 1) * (ll)mask[x][y][8] / 2;
287.                     res_d = res_d % c;
288.                 }
289.             }
290.         }//a-a-a-b
291.        
292.         cout << res_d << " ";
293.        
294.         for(int x = 0; x < n; x++)
295.         {
296.             for(int y = 0; y < n; y++)
297.             {
298.                 if(tab[x][y] == 'a')
299.                 {
300.                     if(mask[x][y][8] >= 1)
301.                     {
302.                         zero_bad();
303.                         for(int i = 0; i < 4; i++)
304.                         {
305.                             if(mask[x][y][2 * i] != -1)
306.                             {
307.                                 neigh(mask[x][y][2 * i],mask[x][y][2 * i + 1],'b');
308.                                 res_d += (ll)(p[8] * (p[8] - 1) / 2);
309.                                 for(int j = 0; j < 4; j++)
310.                                 {
311.                                     if(p[2 * j] != -1)
312.                                     {
313.                                         neigh2(p[2 * j],p[2 * j + 1],'b');
314.                                         int s = 0;
315.                                         for(int h = 0; h < 4; h++)
316.                                             s += check_bad(pp[2 * h],pp[2 * h + 1]);
317.                                         res_d += max(0ll,(ll)(pp[8] - 1 - s));
318.                                     }
319.                                 }
320.                                 bad[2 * i] = mask[x][y][2 * i];
321.                                 bad[2 * i + 1] = mask[x][y][2 * i + 1];
322.                                 chceck_bad_for_replies();
323.                             }
324.                             res_d = res_d % c;
325.                         }
326.                     }
327.                     if(mask[x][y][8] >= 2)
328.                     {
329.                         zero_bad();
330.                         int index = 0;
331.                         for(int i = 0; i < 4; i++)
332.                         {
333.                             if(mask[x][y][2 * i] != -1)
334.                             {
335.                                 for(int j = i + 1; j < 4; j++)
336.                                 {
337.                                     if(mask[x][y][2 * j] != -1)
338.                                     {
339.                                         neigh(mask[x][y][2 * i],mask[x][y][2 * i + 1],'b');
340.                                         res_d += (ll)(p[8] - check_bad(mask[x][y][2 * i],mask[x][y][2 * i + 1]));
341.                                         for(int h = index * 4; (h < (index + 1) * 4 && index < 2); h++)
342.                                         {
343.                                             if(p[(2 * h) % 8] != -1)
344.                                             {
345.                                                 bad[2 * h] = p[(2 * h) % 8];
346.                                                 bad[2 * h + 1] = p [(2 * h + 1) % 8];
347.                                             }
348.                                         }
349.                                         chceck_bad_for_replies();
350.                                         index ++;
351.                                     }
352.                                 }
353.                             }
354.                         }
355.                         res_d = res_d % c;
356.                     }
357.                     if(mask[x][y][8] == 3)
358.                     {
359.                         res_d += 1;
360.                     }
361.                 }
362.                 res_d = res_d % c;
363.             }
364.         }//a-b-b-b
365.        
366.         cout << res_d << " ";
367.        
368.         for(int x = 0; x < n; x++)
369.         {
370.             for(int y = 0; y < n; y++)
371.             {
372.                 if(tab[x][y] == 'a')
373.                 {
374.                     if(mask[x][y][8] > 0)
375.                     {  
376.                         for(int i = 0; i < 4; i++)
377.                         {
378.                             if(mask[x][y][2 * i] != -1)
379.                             {
380.                                 neigh(mask[x][y][2 * i],mask[x][y][2 * i + 1],'b');
381.                                 for(int j = 0; j < 4; j++)
382.                                 {
383.                                     if(p[2 * j] != -1)
384.                                     {
385.                                         neigh2(p[2 * j],p[2 * j + 1],'c');
386.                                         res_d += (ll)(pp[8] * p[8]);
387.                                     }
388.                                 }
389.                             }
390.                         }
391.                         zero_bad();
392.                         for(int h = 0; h < 4; h++)
393.                         {
394.                           bad[2 * h] = mask[x][y][2 * h];
395.                           bad[2 * h + 1] = mask[x][y][2 * h + 1];
396.                         }
397.                         for(int i = 0; i < 4; i++)
398.                         {
399.                             if(mask[x][y][2 * i] != -1)
400.                             {
401.                                 neigh(mask[x][y][2 * i],mask[x][y][2 * i + 1],'c');
402.                                 for(int j = 0; j < 4; j++)
403.                                 {
404.                                     if(p[2 * j] != -1)
405.                                     {
406.                                         neigh2(p[2 * j],p[2 * j + 1],'b');
407.                                         for(int h = 0; h < 4; h++)
408.                                         {
409.                                             if(pp[2 * h] != -1)
410.                                             {
411.                                                 if(check_bad(pp[2 * h],pp[2 * h + 1]) == 0)
412.                                                     res_d += 1;
413.                                             }
414.                                         }
415.                                     }
416.                                 }
417.                             }
418.                         }
419.                    
420.                      
421.                     }
422.                 }
423.             }
424.         }//a-b-c-b
425.        
426.          cout << res_d << " ";
427.        
428.         for(int x = 0; x < n; x++)
429.         {
430.             for(int y = 0; y < n; y++)
431.             {
432.                 if(tab[x][y] == 'a')
433.                 {
434.                     if(mask[x][y][8] >= 2)
435.                     {
436.                         for(int i = 0; i < 4; i++)
437.                         {
438.                             for(int j = i + 1; j < 4; j++)
439.                             {
440.                                 if(mask[x][y][2 * i] != -1 && mask[x][y][2 * j] != -1)
441.                                 {
442.                                     int b_x1 = mask[x][y][2 * i];
443.                                     int b_y1 = mask[x][y][2 * i + 1];
444.                                     int b_x2 = mask[x][y][2 * j];
445.                                     int b_y2 = mask[x][y][2 * j + 1];
446.                                     int count = 0;
447.                                     neigh(b_x1,b_y1,'c');
448.                                     zero_bad();
449.                                     for(int m = 0; m < 4; m++)
450.                                     {
451.                                         bad[2 * m] = p[2 * m];
452.                                         bad[2 * m + 1] = p[2 * m + 1];
453.                                     }
454.                                     neigh2(b_x2,b_y2,'c');
455.                                     for(int m = 0; m < 4; m++)
456.                                     {
457.                                         count += check_bad(pp[2 * m],pp[2 * m + 1]);
458.                                     }
459.                                 res_d += (ll)(p[8] + pp[8] - count);
460.                                 res_d = res_d % c;
461.                                 }
462.                             }
463.                         }
464.                     }
465.                 }
466.             }
467.         }//a-b-b-c
468.        
469.         cout << res_d << " ";
470.        
471.         for(int x = 0; x < n; x++)
472.         {
473.             for(int y = 0; y < n; y++)
474.             {
475.                 if(tab[x][y] == 'a')
476.                 {
477.                     if(mask[x][y][8] > 0)
478.                     {
479.                         for(int i = 0; i < 4; i++)
480.                         {
481.                             if(mask[x][y][2 * i] != -1)
482.                             {
483.                                 neigh(mask[x][y][2 * i],mask[x][y][2 * i],'c');
484.                                 res_d += (ll)(p[8] * (p[8] - 1));
485.                                 for(int j = 0; j < 4; j++)
486.                                 {
487.                                     if(p[2 * j] != -1)
488.                                     {
489.                                         neigh2(p[2 * j],p[2 * j + 1],'c');
490.                                         res_d += (ll)(pp[8] - 1);
491.                                     }
492.                                 }
493.                             }
494.                             res_d = res_d % c;
495.                         }
496.                     }
497.                 }
498.             }
499.         }//a-b-c-c
500.        
501.         cout << res_d << " ";
502.        
503.         for(int x = 0; x < n; x++)
504.         {
505.             for(int y = 0; y < n; y++)
506.             {
507.                 if(tab[x][y] == 'c')
508.                 {
509.                     for(int i = 0; i < 4; i++)
510.                     {
511.                         tp = 0;
512.                         if(mask[x][y][2 * i] != -1)
513.                         {
514.                             tp = max(0ll,res_a - (ll)mask[mask[x][y][2 * i]][mask[x][y][2 * i + 1]][8]);
515.                             res_d += (ll)(mask[mask[x][y][2 * i]][mask[x][y][2 * i + 1]][8] * (mask[mask[x][y][2 * i]][mask[x][y][2 * i + 1]][8] - 1) / 2);
516.                             res_d += (ll)(mask[mask[x][y][2 * i]][mask[x][y][2 * i + 1]][8]) * tp;
517.                             res_d = res_d % c;
518.                         }
519.                     }
520.                    
521.                 }
522.             }
523.         }//a-a-b-c
524.        
525.         cout << res_d << " ";
526.        
527.         for(int x = 0; x < n; x++)
528.         {
529.             for(int y = 0; y < n; y++)
530.             {
531.                 tp = 0;
532.                 if(tab[x][y] == 'a')
533.                 {
534.                     int inter = 0;
535.                     for(int i = 0; i < 4; i++)
536.                     {
537.                         for(int j = i + 1; j < 4; j++)
538.                         {
539.                             if(mask[x][y][2 * i] != -1 && mask[x][y][2 * j] != -1)
540.                             {
541.                                 int b_x1 = mask[x][y][2 * i];
542.                                 int b_y1 = mask[x][y][2 * i + 1];
543.                                 int b_x2 = mask[x][y][2 * j];
544.                                 int b_y2 = mask[x][y][2 * j + 1];
545.                                 int count = 0;
546.                                 neigh(b_x1,b_y1,'a');
547.                                 zero_bad();
548.                                 for(int m = 0; m < 4; m++)
549.                                 {
550.                                     bad[2 * m] = p[2 * m];
551.                                     bad[2 * m + 1] = p[2 * m + 1];
552.                                 }
553.                                 neigh2(b_x2,b_y2,'a');
554.                                 for(int m = 0; m < 4; m++)
555.                                 {
556.                                     count += check_bad(pp[2 * m],pp[2 * m + 1]);
557.                                 }
558.                                 tp = max(0ll, res_a - (ll)(mask[b_x1][b_y1][8] + mask[b_x2][b_y2][8] - count));
559.                                 res_d += tp;
560.                                 res_d = res_d % c;
561.                                 }
562.                             }
563.                         }
564.                     }
565.                 }
566.             } //(a-(b-b) a)
567.        
568.         cout << res_d << " ";
569.        
570.         long long int sq = 0;
571.         long long int sm = 0;
572.         for(int x = 0; x < n; x++)
573.         {
574.             for(int y = 0; y < n; y++)
575.             {
576.                 if(tab[x][y] == 'a')
577.                 {
578.                     sq += (ll)(mask[x][y][8] * mask[x][y][8]);
579.                     sm += (ll)mask[x][y][8];
580.                 }
581.             }
582.         }//pairs
583.         long long int pairs = (sm * sm - sq) / 2;
584.         long long int minus = 0;
585.         for(int x = 0; x < n; x++)
586.         {
587.             for(int y = 0; y < n; y++)
588.             {
589.                 if(tab[x][y] == 'b')
590.                 {
591.                     if(mask[x][y][8] == 2)
592.                         minus += 1;
593.                     if(mask[x][y][8] == 3)
594.                         minus += 3;
595.                 }
596.             }
597.         }//minus
598.         res_d += (pairs - minus) % c;
599.         res_d = res_d % c;
600.         //(a-b)(a-b)
601.        
602.         cout << res_d << " ";
603.        
604.         for(int x = 0; x < n; x++)
605.         {
606.             for(int y = 0; y < n; y++)
607.             {
608.                 if(tab[x][y] == 'b')
609.                 {
610.                     zero_bad();
611.                     for(int h = 0; h < 4; h++)
612.                     {
613.                         bad[2 * h] = mask[x][y][2 * h];
614.                         bad[2 * h + 1] = mask[x][y][2 * h + 1];
615.                     }
616.                     neigh(x,y,'b');
617.                     for(int i = 0; i < 4; i++)
618.                     {
619.                         if(p[2 * i] != -1)
620.                         {
621.                             int ch = 0;
622.                             neigh2(p[2 * i],p[2 * i + 1], 'a');
623.                             for(int j = 0; j < 4; j++)
624.                             {
625.                                 ch += check_bad(pp[2 * j],pp[2 * j + 1]);
626.                             }
627.                             if(ch == 0)
628.                                 res_d += (ll)(mask[x][y][8] * (mask[x][y][8] - 1) / 2);
629.                         }
630.                     }
631.                     res_d = res_d % c;
632.                 }
633.             }
634.         }//(a-a)-b-b
635.        
636.         cout << res_d << " ";
637.        
638.         for(int x = 0; x < n; x++)
639.         {
640.             for(int y = 0; y < n; y++)
641.             {
642.                 if(tab[x][y] == 'b')
643.                 {
644.                     zero_bad();
645.                     for(int h = 0; h < 4; h++)
646.                     {
647.                         bad[2 * h] = mask[x][y][2 * h];
648.                         bad[2 * h + 1] = mask[x][y][2 * h + 1];
649.                     }
650.                     neigh(x,y,'b');
651.                     for(int i = 0; i < 4; i++)
652.                     {
653.                         if(p[2 * i] != -1)
654.                         {
655.                             ll tp = 0;
656.                             for(int h = 0; h < 4; h++)
657.                             {
658.                                 bad[2 * h + 8] = mask[p[2 * i]][p[2 * i + 1]][2 * h];
659.                                 bad[2 * h + 9] = mask[p[2 * i]][p[2 * i + 1]][2 * h + 1];
660.                             }
661.                             chceck_bad_for_replies();
662.                             tp = max(0ll,res_a - (ll)count_bad());
663.                             res_d += tp * (ll)mask[x][y][8];
664.                             res_d = res_d % c;
665.                         }
666.                     }
667.                 }
668.             }
669.         }//a-b-b a
670.        
671.         cout << res_d;
672.     }
673.    
674.     return 0;
675. }
676.