#include <iostream>
using namespace std;
typedef int long long ll;
char tab[3000][3000];
short int mask[3000][3000][9];
short int nx[] = {-1, 1, 0, 0};
short int ny[] = {0, 0, 1, -1};
int n, k;
short int p[] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
short int pp[] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
short int bad[] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
const long long int c = 1e9 + 7;
bool if_fits(int x, int y){
if(x >= 0 && x < n && y >= 0 && y < n)
return 1;
else
return 0;
}
void neigh(int x, int y, char letter){
p[8] = 0;
for(int i = 0; i < 4; i++)
{
if(if_fits((x + nx[i]),(y + ny[i])) && tab[x + nx[i]][y + ny[i]] == letter)
{
p[2 * i] = x + nx[i];
p[2 * i + 1] = y + ny[i];
p[8] += 1;
}else{
p[2 * i] = -1;
}
}
}
void neigh2(int x, int y, char letter){
pp[8] = 0;
for(int i = 0; i < 4; i++)
{
if(if_fits((x + nx[i]),(y + ny[i])) && tab[x + nx[i]][y + ny[i]] == letter)
{
pp[2 * i] = x + nx[i];
pp[2 * i + 1] = y + ny[i];
pp[8] += 1;
}else{
pp[2 * i] = -1;
}
}
}
void zero_bad(){
for(int i = 0; i < 16; i++)
{
bad[i] = -1;
}
}
int check_bad(int x, int y){
int res = 0;
for(int i = 0; i < 8; i++)
{
if(bad[2 * i] != -1)
{
if(bad[2 * i] == x && bad[2 * i + 1] == y)
res += 1;
}
}
return res;
}
void chceck_bad_for_replies(){
for(int i = 0; i < 8; i++)
{
for(int j = i + 1; j < 8; j++)
{
if(bad[2 * i] == bad[2 * j] && bad[2 * i + 1] == bad[2 * j + 1])
bad[2 * j] = -1;
}
}
}
int count_bad(){
int res = 0;
for(int i = 0; i < 8; i++)
{
if(bad[2 * i] != -1)
res += 1;
}
return res;
}
int main()
{
cin >> n >> k;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cin >> tab[i][j];
for(int l = 0; l < 27; l++)
{
mask[i][j][l] = 0;
}
}
}//wczytanie
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++)
{
if(tab[x][y] == '.')
{
for(int i = 0; i < 4; i++)
{
if(if_fits(x + nx[i], y + ny[i]) && tab[x + nx[i]][y + ny[i]] == '#')
{
tab[x][y] = 'a';
}
else
mask[x][y][2 * i] = -1;
}
}
}
}//wpisanie a
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++)
{
if(tab[x][y] == '.')
{
for(int i = 0; i < 4; i++)
{
if(if_fits(x + nx[i], y + ny[i]) && tab[x + nx[i]][y + ny[i]] == 'a')
{
mask[x][y][8] += 1;
mask[x][y][2 * i] = x + nx[i];
mask[x][y][2 * i + 1] = y + ny[i];
tab[x][y] = 'b';
}
else
mask[x][y][2 * i] = -1;
}
}
}
}//wpisanie b
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++)
{
if(tab[x][y] == '.')
{
for(int i = 0; i < 4; i++)
{
if(if_fits(x + nx[i], y + ny[i]) && tab[x + nx[i]][y + ny[i]] == 'b')
{
mask[x][y][8] += 1;
mask[x][y][2 * i] = x + nx[i];
mask[x][y][2 * i + 1] = y + ny[i];
tab[x][y] = 'c';
}
else
mask[x][y][2 * i] = -1;
}
}
}
}//wpisanie c
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++)
{
if(tab[x][y] == '.')
{
for(int i = 0; i < 4; i++)
{
if(if_fits(x + nx[i], y + ny[i]) && tab[x + nx[i]][y + ny[i]] == 'c')
{
mask[x][y][8] += 1;
mask[x][y][2 * i] = x + nx[i];
mask[x][y][2 * i + 1] = y + ny[i];
tab[x][y] = 'd';
}
else
mask[x][y][2 * i] = -1;
}
}
}
}//wpisanie d
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++)
{
if(tab[x][y] == 'a')
{
for(int i = 0; i < 4; i++)
{
if(if_fits(x + nx[i], y + ny[i]) && tab[x + nx[i]][y + ny[i]] == 'b')
{
mask[x][y][8] += 1;
mask[x][y][2 * i] = x + nx[i];
mask[x][y][2 * i + 1] = y + ny[i];
}
else
mask[x][y][2 * i] = -1;
}
}
}
}//poprawienie maski dla a
long long int res_a = 0;
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++)
{
if(tab[x][y] == 'a')
res_a += 1;
}
}//res_a
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cout << tab[i][j] << " ";
}
cout << endl;
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
for(int l = 0; l < 9; l++)
{
cout << mask[i][j][l] << " ";
}
cout<<endl;
}
cout<<endl;
}
if(k == 4)
{
long long int tp;
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
res_d = res_d % c;
cout << res_d << " ";
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++)
{
if(tab[x][y] == 'd')
{
for(int i = 0; i < 4; i++)
{
if(mask[x][y][2 * i] != -1)
{
for(int j = 0; j < 4; j++)
{
if(mask[mask[x][y][2 * i]][mask[x][y][2 * i + 1]][2 * j] != -1)
{
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];
res_d = res_d % c;
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] << "|";
}
}
}
}
}
}
}//a-b-c-d
cout << res_d << " ";
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++)
{
tp = 0;
if(tab[x][y] == 'b')
{
res_d += (ll)(mask[x][y][8] * (mask[x][y][8] - 1) * (mask[x][y][8] - 2) / 6);
tp = max(0ll,res_a - (ll)mask[x][y][8]);
res_d += tp * (ll)(mask[x][y][8] * (mask[x][y][8] - 1) / 2);
res_d = res_d % c;
res_d += tp * (tp - 1) * (ll)mask[x][y][8] / 2;
res_d = res_d % c;
}
}
}//a-a-a-b
cout << res_d << " ";
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++)
{
if(tab[x][y] == 'a')
{
if(mask[x][y][8] >= 1)
{
zero_bad();
for(int i = 0; i < 4; i++)
{
if(mask[x][y][2 * i] != -1)
{
neigh(mask[x][y][2 * i],mask[x][y][2 * i + 1],'b');
res_d += (ll)(p[8] * (p[8] - 1) / 2);
for(int j = 0; j < 4; j++)
{
if(p[2 * j] != -1)
{
neigh2(p[2 * j],p[2 * j + 1],'b');
int s = 0;
for(int h = 0; h < 4; h++)
s += check_bad(pp[2 * h],pp[2 * h + 1]);
res_d += max(0ll,(ll)(pp[8] - 1 - s));
}
}
bad[2 * i] = mask[x][y][2 * i];
bad[2 * i + 1] = mask[x][y][2 * i + 1];
chceck_bad_for_replies();
}
res_d = res_d % c;
}
}
if(mask[x][y][8] >= 2)
{
zero_bad();
int index = 0;
for(int i = 0; i < 4; i++)
{
if(mask[x][y][2 * i] != -1)
{
for(int j = i + 1; j < 4; j++)
{
if(mask[x][y][2 * j] != -1)
{
neigh(mask[x][y][2 * i],mask[x][y][2 * i + 1],'b');
res_d += (ll)(p[8] - check_bad(mask[x][y][2 * i],mask[x][y][2 * i + 1]));
for(int h = index * 4; (h < (index + 1) * 4 && index < 2); h++)
{
if(p[(2 * h) % 8] != -1)
{
bad[2 * h] = p[(2 * h) % 8];
bad[2 * h + 1] = p [(2 * h + 1) % 8];
}
}
chceck_bad_for_replies();
index ++;
}
}
}
}
res_d = res_d % c;
}
if(mask[x][y][8] == 3)
{
res_d += 1;
}
}
res_d = res_d % c;
}
}//a-b-b-b
cout << res_d << " ";
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++)
{
if(tab[x][y] == 'a')
{
if(mask[x][y][8] > 0)
{
for(int i = 0; i < 4; i++)
{
if(mask[x][y][2 * i] != -1)
{
neigh(mask[x][y][2 * i],mask[x][y][2 * i + 1],'b');
for(int j = 0; j < 4; j++)
{
if(p[2 * j] != -1)
{
neigh2(p[2 * j],p[2 * j + 1],'c');
res_d += (ll)(pp[8] * p[8]);
}
}
}
}
zero_bad();
for(int h = 0; h < 4; h++)
{
bad[2 * h] = mask[x][y][2 * h];
bad[2 * h + 1] = mask[x][y][2 * h + 1];
}
for(int i = 0; i < 4; i++)
{
if(mask[x][y][2 * i] != -1)
{
neigh(mask[x][y][2 * i],mask[x][y][2 * i + 1],'c');
for(int j = 0; j < 4; j++)
{
if(p[2 * j] != -1)
{
neigh2(p[2 * j],p[2 * j + 1],'b');
for(int h = 0; h < 4; h++)
{
if(pp[2 * h] != -1)
{
if(check_bad(pp[2 * h],pp[2 * h + 1]) == 0)
res_d += 1;
}
}
}
}
}
}
}
}
}
}//a-b-c-b
cout << res_d << " ";
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++)
{
if(tab[x][y] == 'a')
{
if(mask[x][y][8] >= 2)
{
for(int i = 0; i < 4; i++)
{
for(int j = i + 1; j < 4; j++)
{
if(mask[x][y][2 * i] != -1 && mask[x][y][2 * j] != -1)
{
int b_x1 = mask[x][y][2 * i];
int b_y1 = mask[x][y][2 * i + 1];
int b_x2 = mask[x][y][2 * j];
int b_y2 = mask[x][y][2 * j + 1];
int count = 0;
neigh(b_x1,b_y1,'c');
zero_bad();
for(int m = 0; m < 4; m++)
{
bad[2 * m] = p[2 * m];
bad[2 * m + 1] = p[2 * m + 1];
}
neigh2(b_x2,b_y2,'c');
for(int m = 0; m < 4; m++)
{
count += check_bad(pp[2 * m],pp[2 * m + 1]);
}
res_d += (ll)(p[8] + pp[8] - count);
res_d = res_d % c;
}
}
}
}
}
}
}//a-b-b-c
cout << res_d << " ";
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++)
{
if(tab[x][y] == 'a')
{
if(mask[x][y][8] > 0)
{
for(int i = 0; i < 4; i++)
{
if(mask[x][y][2 * i] != -1)
{
neigh(mask[x][y][2 * i],mask[x][y][2 * i],'c');
res_d += (ll)(p[8] * (p[8] - 1));
for(int j = 0; j < 4; j++)
{
if(p[2 * j] != -1)
{
neigh2(p[2 * j],p[2 * j + 1],'c');
res_d += (ll)(pp[8] - 1);
}
}
}
res_d = res_d % c;
}
}
}
}
}//a-b-c-c
cout << res_d << " ";
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++)
{
if(tab[x][y] == 'c')
{
for(int i = 0; i < 4; i++)
{
tp = 0;
if(mask[x][y][2 * i] != -1)
{
tp = max(0ll,res_a - (ll)mask[mask[x][y][2 * i]][mask[x][y][2 * i + 1]][8]);
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);
res_d += (ll)(mask[mask[x][y][2 * i]][mask[x][y][2 * i + 1]][8]) * tp;
res_d = res_d % c;
}
}
}
}
}//a-a-b-c
cout << res_d << " ";
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++)
{
tp = 0;
if(tab[x][y] == 'a')
{
int inter = 0;
for(int i = 0; i < 4; i++)
{
for(int j = i + 1; j < 4; j++)
{
if(mask[x][y][2 * i] != -1 && mask[x][y][2 * j] != -1)
{
int b_x1 = mask[x][y][2 * i];
int b_y1 = mask[x][y][2 * i + 1];
int b_x2 = mask[x][y][2 * j];
int b_y2 = mask[x][y][2 * j + 1];
int count = 0;
neigh(b_x1,b_y1,'a');
zero_bad();
for(int m = 0; m < 4; m++)
{
bad[2 * m] = p[2 * m];
bad[2 * m + 1] = p[2 * m + 1];
}
neigh2(b_x2,b_y2,'a');
for(int m = 0; m < 4; m++)
{
count += check_bad(pp[2 * m],pp[2 * m + 1]);
}
tp = max(0ll, res_a - (ll)(mask[b_x1][b_y1][8] + mask[b_x2][b_y2][8] - count));
res_d += tp;
res_d = res_d % c;
}
}
}
}
}
} //(a-(b-b) a)
cout << res_d << " ";
long long int sq = 0;
long long int sm = 0;
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++)
{
if(tab[x][y] == 'a')
{
sq += (ll)(mask[x][y][8] * mask[x][y][8]);
sm += (ll)mask[x][y][8];
}
}
}//pairs
long long int pairs = (sm * sm - sq) / 2;
long long int minus = 0;
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++)
{
if(tab[x][y] == 'b')
{
if(mask[x][y][8] == 2)
minus += 1;
if(mask[x][y][8] == 3)
minus += 3;
}
}
}//minus
res_d += (pairs - minus) % c;
res_d = res_d % c;
//(a-b)(a-b)
cout << res_d << " ";
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++)
{
if(tab[x][y] == 'b')
{
zero_bad();
for(int h = 0; h < 4; h++)
{
bad[2 * h] = mask[x][y][2 * h];
bad[2 * h + 1] = mask[x][y][2 * h + 1];
}
neigh(x,y,'b');
for(int i = 0; i < 4; i++)
{
if(p[2 * i] != -1)
{
int ch = 0;
neigh2(p[2 * i],p[2 * i + 1], 'a');
for(int j = 0; j < 4; j++)
{
ch += check_bad(pp[2 * j],pp[2 * j + 1]);
}
if(ch == 0)
res_d += (ll)(mask[x][y][8] * (mask[x][y][8] - 1) / 2);
}
}
res_d = res_d % c;
}
}
}//(a-a)-b-b
cout << res_d << " ";
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++)
{
if(tab[x][y] == 'b')
{
zero_bad();
for(int h = 0; h < 4; h++)
{
bad[2 * h] = mask[x][y][2 * h];
bad[2 * h + 1] = mask[x][y][2 * h + 1];
}
neigh(x,y,'b');
for(int i = 0; i < 4; i++)
{
if(p[2 * i] != -1)
{
ll tp = 0;
for(int h = 0; h < 4; h++)
{
bad[2 * h + 8] = mask[p[2 * i]][p[2 * i + 1]][2 * h];
bad[2 * h + 9] = mask[p[2 * i]][p[2 * i + 1]][2 * h + 1];
}
chceck_bad_for_replies();
tp = max(0ll,res_a - (ll)count_bad());
res_d += tp * (ll)mask[x][y][8];
res_d = res_d % c;
}
}
}
}
}//a-b-b a
cout << res_d;
}
return 0;
}