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
#include <bits/stdc++.h>

using namespace std;

int n, k;
char tab[3005][3005];

// int mod = 1000000007;
int mod = 1000*1000*1000+7;

bool dasie(int x, int y) {
    if(tab[x][y]!='#' && (tab[x+1][y]=='#' || tab[x-1][y]=='#' || tab[x][y+1]=='#' || tab[x][y-1]=='#')) return true;
    return false;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    srand(n);
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            cin >> tab[i][j];
        }
    }
    if(k==1) {
        long long wyn=0;
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(dasie(i, j)) {
                    wyn++;
                    wyn%=mod;
                }
            }
        }
        cout << wyn << "\n";
    }
    if(k==2) {
        long long wyn = 0;
        set<set<int> > s;
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                set<int> secik;
                if(dasie(i, j)) {
                    secik.insert(i*n+j);
                    tab[i][j]='#';
                    for(int ki=1; ki<=n; ki++) {
                        for(int kj=1; kj<=n; kj++) {
                            if(dasie(ki, kj)) {
                                secik.insert(ki*n+kj);
                                if(s.find(secik)==s.end()) {
                                    wyn++;
                                    wyn%=mod;
                                    s.insert(secik);
                                }
                                secik.erase(ki*n+kj);
                            }
                        }
                    }
                    tab[i][j]='.';
                    secik.erase(i*n+j);
                }
            }
        }
        cout << wyn << "\n";
    }
    if(k==3) {
        long long wyn = 0;
        set<set<int> > s;
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                set<int> secik;
                if(dasie(i, j)) {
                    secik.insert(i*n+j);
                    tab[i][j]='#';
                    for(int ki=1; ki<=n; ki++) {
                        for(int kj=1; kj<=n; kj++) {
                            if(dasie(ki, kj)) {
                                secik.insert(ki*n+kj);
                                tab[ki][kj]='#';
                                for(int li=1; li<=n; li++) {
                                    for(int lj=1; lj<=n; lj++) {
                                        if(dasie(li, lj)) {
                                            secik.insert(li*n+lj);
                                            if(s.find(secik)==s.end()) {
                                                // tab[li][lj]='#';
                                                // for(int adf=1; adf<=n; adf++) {
                                                //     for(int l=1; l<=n; l++){
                                                //         cout << tab[adf][l];
                                                //     }
                                                //     cout << "\n";
                                                // }
                                                // cout << "\n";
                                                // tab[li][lj]='.';
                                                wyn++;
                                                wyn%=mod;
                                                s.insert(secik);
                                            }
                                            secik.erase(li*n+lj);
                                        }
                                    }
                                }
                                tab[ki][kj]='.';
                                secik.erase(ki*n+kj);
                            }
                        }
                    }
                    tab[i][j]='.';
                    secik.erase(i*n+j);
                }
            }
        }
        cout << wyn << "\n";
    }
    if(k==4) {
        cout << "4!\n";
        long long wyn = 0;
        set<set<int> > s;
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                set<int> secik;
                if(dasie(i, j)) {
                    secik.insert(i*n+j);
                    tab[i][j]='#';
                    for(int ki=1; ki<=n; ki++) {
                        for(int kj=1; kj<=n; kj++) {
                            if(dasie(ki, kj)) {
                                secik.insert(ki*n+kj);
                                tab[ki][kj]='#';
                                for(int li=1; li<=n; li++) {
                                    for(int lj=1; lj<=n; lj++) {
                                        if(dasie(li, lj)) {
                                            secik.insert(li*n+lj);
                                            tab[li][lj]='#';
                                            for(int mi=1; mi<=n; mi++) {
                                                for(int mj=1; mj<=n; mj++) {
                                                    if(dasie(mi, mj)) {
                                                        secik.insert(mi*n+mj);
                                                        if(s.find(secik)==s.end()) {
                                                            // tab[mi][mj]='#';
                                                            // for(int adf=1; adf<=n; adf++) {
                                                            //     for(int l=1; l<=n; l++){
                                                            //         cout << tab[adf][l];
                                                            //     }
                                                            //     cout << "\n";
                                                            // }
                                                            // cout << "\n";
                                                            // tab[mi][mj]='.';
                                                            wyn++;
                                                            wyn%=mod;
                                                            s.insert(secik);
                                                        }
                                                        secik.erase(mi*n+mj);
                                                    }
                                                }
                                            }
                                            tab[li][lj]='.';
                                            secik.erase(li*n+lj);
                                        }
                                    }
                                }
                                tab[ki][kj]='.';
                                secik.erase(ki*n+kj);
                            }
                        }
                    }
                    tab[i][j]='.';
                    secik.erase(i*n+j);
                }
            }
        }
        cout << wyn << "\n";
    }
}