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
#include<cstdio>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;

#define st first
#define nd second

int n, k;

char tab [3007][3007];
char in [3007];

vector < pair < int, int > > v;
vector < pair < int, int > > p;
set < vector < pair < int , int > > > s;

pair < int, int > t[17] = { {0,1}, {1,0}, {-1,0}, {0,-1} };

bool b(pair < int, int > x){
    if( (x.st < 1) or (x.st > n) )
        return false;
    if( (x.nd < 1) or (x.nd > n) )
        return false;
    if(tab[x.st][x.nd] == '#')
        return false;
    return true;
}

vector < pair < int, int > > sas(pair < int , int > x){
    vector < pair < int , int > > w;
    w.clear();
    for(int i = 0;i < 4; i++){
        if( b({ x.st + t[i].st, x.nd + t[i].nd }) )
            w.push_back({x.st + t[i].st, x.nd + t[i].nd});
    }

    return w;
}

void f(){
    if( (int)p.size() == k){
        vector < pair < int ,int > > ech = p;
        sort(ech.begin(),ech.end());
        s.insert(ech);
        return;
    }

    vector < pair < int , int > > pom;
    pom.clear();
    for(auto x : v){
        for(auto y : sas(x)){
            pom.push_back(y);
        }
    }

    sort(pom.begin(),pom.end());
    for(int i = 0;i < pom.size(); i++){
        if(i != (int)pom.size() - 1){
            if(pom[i] == pom[i + 1])
                continue;
        }

        pair < int, int > y = pom[i];

        v.push_back(y);
        p.push_back(y);
        tab[y.st][y.nd] = '#';
        f();
        tab[y.st][y.nd] = '.';
        v.pop_back();
        p.pop_back();
    }

    return;
}

int main(){
    scanf("%d %d",&n,&k);

    for(int i = 1;i <= n; i++){
        scanf("%s",in);

        for(int j = 0;j < n; j++){
            tab[i][j + 1] = in[j];
        }
    }

    for(int i = 1;i <= n; i++){
        for(int j = 1;j <= n; j++){
            if( (tab[i][j] == '#') and ((int)sas({i,j}).size() > 0) )
                v.push_back({i,j});
        }
    }

    f();
    printf("%d\n", (int)s.size() % 1000000007);

    return 0;
}