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
#include <bits/stdc++.h>
using namespace std;
int n, k, W, it;
char z;
set <vector <vector <bool > > > S;
const int modulo = 1000000007;
int SS, maps[3003][3003], P[5];
vector <int> Two;
set <vector <pair <int, int> > > Comb[5];
void go(vector <vector <bool> > T, int steps){
    if (steps == k){
        W ++;
     /*/   if (!S.count(T)){
            cout << endl << ++it << endl;
            for (int i = 0; i < n; i ++){
                for (int j = 0; j < n; j ++)
                    cout << T[i][j] << " ";
                cout << endl;
            }
        }
        /*/
        S.insert(T);
        return;
    }
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            if (!T[i][j] and ((j > 0 and T[i][j - 1]) or (i > 0 and T[i - 1][j]) or T[i + 1][j] or T[i][j + 1])){
                T[i][j] = true;
                go(T, steps + 1);
                T[i][j] = false;
            }
}
void BFS(){
    queue <pair <int, int> > Q;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            if (maps[i][j] == 0)
                Q.push(make_pair(i, j));
    while (!Q.empty()){
        int current_1 = Q.front().first;
        int current_2 = Q.front().second;
        Q.pop();
        for (int i = current_1 - 1; i <= current_1 + 1; i ++)
            for (int j = current_2 - 1; j <= current_2 + 1; j ++)
                if (abs(i - current_1 + j - current_2) == 1)        
                    if (0 <= min(i, j) and max(i, j) < n)
                        if (maps[i][j] == -1){
                            maps[i][j] = maps[current_1][current_2] + 1;
                            Q.push(make_pair(i, j));
                        }    
    }
}
void Input(){  
    for (int i = 0; i < n; i ++){
            for (int j = 0; j < n; j ++){
            char z;
            scanf("%c", &z);
            if (z == '.')
                maps[i][j] = -1;        
        }
      //  cout << i << endl;
        scanf("\n");
    }
}
void Simulation(vector <pair <int, int > > X){
    for (int i = 1; i < X.size(); i ++)
         if (X[i] == X[i - 1])
            return;
    Comb[X.size()].insert(X);
 /*/   if (X.size() == k){
        for (int i = 0 ; i < X.size(); i ++)
            cout << "(" << X[i].first << ", " << X[i].second << ") ";
        cout << endl;
    }/*/
    if (X.size() == k) return;
    for (int i = 0; i < X.size(); i ++)
        for (int j = X[i].first - 1; j <= X[i].first + 1; j ++)
            for (int o = X[i].second - 1; o <= X[i].second + 1; o ++)
                if (abs(j - X[i].first + o - X[i].second) == 1)
                    if (0 <= min(j, o) and max(j, o) < n)
                        if (maps[X[i].first][X[i].second] < maps[j][o]){
                            vector <pair <int, int > > Y = X;
                            Y.push_back(make_pair(j, o));
                            sort(Y.begin(), Y.end());
                            if (!Comb[Y.size()].count(Y))
                                Simulation(Y);
                        }                            
}
void go1(){
    ios_base::sync_with_stdio(false);
    Input();
    BFS();
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            if (maps[i][j] == 1){
                vector <pair <int, int > > Y;
                Y.clear();
                Y.push_back(make_pair(i, j));
                for (int o = 0; o < 5; o ++)
                    Comb[o].clear();
                Simulation(Y);
                for (int o = 1; o < 5; o ++)
                    P[o] += Comb[o].size();
                Two.push_back(Comb[2].size());
            }
    if (k == 1)
        SS = P[1];
    if (k == 2){
        SS += (P[1] * P[1] - P[1]) / 2;
       // S %= modulo;
        SS += P[2];
       // S %= modulo;
    }
    SS %= modulo;
    cout << SS;
}
int main(){
   // ios_base::sync_with_stdio(false);
    scanf("%d%d\n", &n, &k);
    if (k < 3){
        go1();
        return 0;   
    }
   // cout << "PYK";
    vector <vector <bool> > T;
    vector <bool> Y;
    for (int i = 0; i <= n + 1; i ++)
        Y.push_back(false);
    for (int i = 0; i <= n + 1; i ++)
        T.push_back(Y);
    
    
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j++){
            cin >> z;
            if (z == '#')
                T[i][j] = true;
        } 
    go(T, 0);
    cout << S.size();    
    return 0;
}