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
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
#include <iostream>
#include <vector>

using namespace std;

struct possition {
    int x, y;
};


int main() {
    int n, k;
    cin >> n >> k;

    vector<vector<int>> empty_board(n + 2);
    for (int count = 0; count < n + 2; count++) {
        if (count == 0 or count == n + 1) {
            for (int count2 = 0; count2 < n + 2; count2++) {
                empty_board[count].push_back(2);
            }
        } else {
            for (int count2 = 0; count2 < n + 2; count2++) {

                if (count2 == 0 or count2 == n + 1) {
                    empty_board[count].push_back(2);
                } else {
                    char temp;
                    cin >> temp;
                    if (temp == '#') {
                        empty_board[count].push_back(1);
                    } else if (temp == '.') {
                        empty_board[count].push_back(0);
                    }
                }
            }
        }
    }
    possition start;
    start.x = 1;
    start.y = 1;
    uint64_t options = 0;
    vector<vector<int>> empty_board_temp = empty_board;
    if (k == 1) {
        for (int count1 = start.x; count1 < n + 1; count1++) {
            for (int count2 = start.y; count2 < n + 1; count2++) {
                //cout << empty_board_temp[count1][count2] << " " << options << '\n';
                if (empty_board_temp[count1][count2] == 0 && (empty_board_temp[count1 + 1][count2] == 1 ||
                                                              empty_board_temp[count1][count2 + 1] == 1 ||
                                                              empty_board_temp[count1 - 1][count2] == 1 ||
                                                              empty_board_temp[count1][count2 - 1] == 1)) {
                    options++;
                    /*empty_board_temp[count1][count2] = 1;
                    for (int countx = 0; countx < n + 2; countx++) {
                        for (int county = 0; county < n + 2; county++) {
                            cout << empty_board_temp[countx][county] << " ";
                        }
                        cout << '\n';
                    }
                    empty_board_temp[count1][count2] = 0;
                    cout << '\n';*/
                }
            }
        }
    } else if (k == 2) {
        for (int count1 = start.x; count1 < n + 1; count1++) {
            for (int count2 = start.y; count2 < n + 1; count2++) {
                //cout << empty_board_temp[count1][count2] << " " << options << '\n';
                if (empty_board_temp[count1][count2] == 0 && (empty_board_temp[count1 + 1][count2] == 1 ||
                                                              empty_board_temp[count1][count2 + 1] == 1 ||
                                                              empty_board_temp[count1 - 1][count2] == 1 ||
                                                              empty_board_temp[count1][count2 - 1] == 1)) {
                    empty_board_temp[count1][count2] = 1;
                    possition start_temp1;
                    start_temp1.x = count1;
                    start_temp1.y = count2;
                    for (int count3 = start_temp1.x; count3 < n + 1; count3++) {
                        for (int count4 = start_temp1.y; count4 < n + 1; count4++) {
                            //cout << empty_board_temp[count1][count2] << " " << options << '\n';
                            if (empty_board_temp[count3][count4] == 0 && (empty_board_temp[count3 + 1][count4] == 1 ||
                                                                          empty_board_temp[count3][count4 + 1] == 1 ||
                                                                          empty_board_temp[count3 - 1][count4] == 1 ||
                                                                          empty_board_temp[count3][count4 - 1] == 1)) {
                                options++;
                                /*empty_board_temp[count3][count4] = 1;
                                for (int countx = 0; countx < n + 2; countx++) {
                                    for (int county = 0; county < n + 2; county++) {
                                        cout << empty_board_temp[countx][county] << " ";
                                    }
                                    cout << '\n';
                                }
                                empty_board_temp[count3][count4] = 0;
                                cout << '\n';*/
                            }
                        }
                        start_temp1.y = 0;
                    }
                    empty_board_temp[count1][count2] = 0;
                }
            }
        }
    } else if (k == 3) {
        for (int count1 = start.x; count1 < n + 1; count1++) {
            for (int count2 = start.y; count2 < n + 1; count2++) {
                //cout << empty_board_temp[count1][count2] << " " << options << '\n';
                if (empty_board_temp[count1][count2] == 0 && (empty_board_temp[count1 + 1][count2] == 1 ||
                                                              empty_board_temp[count1][count2 + 1] == 1 ||
                                                              empty_board_temp[count1 - 1][count2] == 1 ||
                                                              empty_board_temp[count1][count2 - 1] == 1)) {
                    empty_board_temp[count1][count2] = 1;
                    possition start_temp1;
                    start_temp1.x = count1;
                    start_temp1.y = count2;
                    for (int count3 = start_temp1.x; count3 < n + 1; count3++) {
                        for (int count4 = start_temp1.y; count4 < n + 1; count4++) {
                            //cout << empty_board_temp[count1][count2] << " " << options << '\n';
                            if (empty_board_temp[count3][count4] == 0 && (empty_board_temp[count3 + 1][count4] == 1 ||
                                                                          empty_board_temp[count3][count4 + 1] == 1 ||
                                                                          empty_board_temp[count3 - 1][count4] == 1 ||
                                                                          empty_board_temp[count3][count4 - 1] == 1)) {
                                empty_board_temp[count3][count4] = 1;
                                possition start_temp2;
                                start_temp2.x = count3;
                                start_temp2.y = count4;
                                for (int count5 = start_temp2.x; count5 < n + 1; count5++) {
                                    for (int count6 = start_temp2.y; count6 < n + 1; count6++) {
                                        //cout << empty_board_temp[count1][count2] << " " << options << '\n';
                                        if (empty_board_temp[count5][count6] == 0 &&
                                            (empty_board_temp[count5 + 1][count6] == 1 ||
                                             empty_board_temp[count5][count6 + 1] == 1 ||
                                             empty_board_temp[count5 - 1][count6] == 1 ||
                                             empty_board_temp[count5][count6 - 1] ==
                                             1)) {
                                            options++;
                                            /*empty_board_temp[count5][count6] = 1;
                                            for (int countx = 0; countx < n + 2; countx++) {
                                                for (int county = 0; county < n + 2; county++) {
                                                    cout << empty_board_temp[countx][county] << " ";
                                                }
                                                cout << '\n';
                                            }
                                            empty_board_temp[count5][count6] = 0;
                                            cout << '\n';*/
                                        }
                                    }
                                    start_temp2.y = 0;
                                }
                                empty_board_temp[count3][count4] = 0;
                            }
                        }
                        start_temp1.y = 0;
                    }
                    empty_board_temp[count1][count2] = 0;
                }
            }
        }
    } else if (k == 4) {
        for (int count1 = start.x; count1 < n + 1; count1++) {
            for (int count2 = start.y; count2 < n + 1; count2++) {
                //cout << empty_board_temp[count1][count2] << " " << options << '\n';
                if (empty_board_temp[count1][count2] == 0 && (empty_board_temp[count1 + 1][count2] == 1 ||
                                                              empty_board_temp[count1][count2 + 1] == 1 ||
                                                              empty_board_temp[count1 - 1][count2] == 1 ||
                                                              empty_board_temp[count1][count2 - 1] == 1)) {
                    empty_board_temp[count1][count2] = 1;
                    possition start_temp1;
                    start_temp1.x = count1;
                    start_temp1.y = count2;
                    for (int count3 = start_temp1.x; count3 < n + 1; count3++) {
                        for (int count4 = start_temp1.y; count4 < n + 1; count4++) {
                            //cout << empty_board_temp[count1][count2] << " " << options << '\n';
                            if (empty_board_temp[count3][count4] == 0 && (empty_board_temp[count3 + 1][count4] == 1 ||
                                                                          empty_board_temp[count3][count4 + 1] == 1 ||
                                                                          empty_board_temp[count3 - 1][count4] == 1 ||
                                                                          empty_board_temp[count3][count4 - 1] == 1)) {
                                empty_board_temp[count3][count4] = 1;
                                possition start_temp2;
                                start_temp2.x = count3;
                                start_temp2.y = count4;
                                for (int count5 = start_temp2.x; count5 < n + 1; count5++) {
                                    for (int count6 = start_temp2.y; count6 < n + 1; count6++) {
                                        //cout << empty_board_temp[count1][count2] << " " << options << '\n';
                                        if (empty_board_temp[count5][count6] == 0 &&
                                            (empty_board_temp[count5 + 1][count6] == 1 ||
                                             empty_board_temp[count5][count6 + 1] == 1 ||
                                             empty_board_temp[count5 - 1][count6] == 1 ||
                                             empty_board_temp[count5][count6 - 1] ==
                                             1)) {
                                            empty_board_temp[count5][count6] = 1;
                                            possition start_temp3;
                                            start_temp3.x = count5;
                                            start_temp3.y = count6;
                                            for (int count7 = start_temp3.x; count7 < n + 1; count7++) {
                                                for (int count8 = start_temp3.y; count8 < n + 1; count8++) {
                                                    //cout << empty_board_temp[count1][count2] << " " << options << '\n';
                                                    if (empty_board_temp[count7][count8] == 0 &&
                                                        (empty_board_temp[count7 + 1][count8] == 1 ||
                                                         empty_board_temp[count7][count8 + 1] == 1 ||
                                                         empty_board_temp[count7 - 1][count8] == 1 ||
                                                         empty_board_temp[count7][count8 - 1] == 1)) {
                                                        options++;
                                                        /*empty_board_temp[count7][count8] = 1;
                                                        for (int countx = 0; countx < n + 2; countx++) {
                                                            for (int county = 0; county < n + 2; county++) {
                                                                cout << empty_board_temp[countx][county] << " ";
                                                            }
                                                            cout << '\n';
                                                        }
                                                        empty_board_temp[count7][count8] = 0;
                                                        cout << '\n';*/
                                                    }
                                                }
                                                start_temp3.y = 0;
                                            }
                                            empty_board_temp[count5][count6] = 0;
                                        }
                                    }
                                    start_temp2.y = 0;
                                }
                                empty_board_temp[count3][count4] = 0;
                            }
                        }
                        start_temp1.y = 0;
                    }
                    empty_board_temp[count1][count2] = 0;
                }
            }
        }
    }


    cout << options % (1000000007) << '\n';


    return 0;
}