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
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
#define MAXN 3007
#define P (1000LL*1000LL*1000LL + 7LL)
char tab[MAXN][MAXN];  //x, y 
int n, k;
typedef long long ll;
int rx[]={0,0,1,-1}, ry[]={1,-1,0,0};
inline bool wewnatrz(const int &x,const int &y) {
  return (x >= 0 && x < n && y >= 0 && y < n);
}
vector<pair<int,int>> dodane;
bool vis[5];
ll licz(int x, int y, int zostalo) {
  if (x >= n) return 0;
  assert(tab[x][y] == '.');
  tab[x][y] = '#';
  dodane.push_back(make_pair(x,y));
//  printf("w %d %d %d\n", x, y, zostalo);
  if (zostalo == 1){
    ll res = 1ll;
 //   for(int i = 0; i < n; i++) printf("%s\n", tab[i]);
//    printf("\n");
    assert(dodane.size() == k);
    for(int i = 0; i < dodane.size(); i++){
      pair<int,int> fr = dodane[i];
      queue<int> kol;
      kol.push(i);
      for(int j = 0; j < k; j++) vis[j] = false;
      bool has = false;
      while((!has) && (!kol.empty())) {
        pair<int,int> elem = dodane[kol.front()];
        kol.pop();
        for(int r = 0; r < 4; r++){
          int nx = elem.first + rx[r], ny = elem.second + ry[r];
          if ((not wewnatrz(nx, ny)) || tab[nx][ny] == '.') continue;
          bool inny = true;
          for (int j = 0; j < dodane.size(); j++) {
            if (dodane[j] == make_pair(nx, ny)) {
              inny = false;
              if (!vis[j]){
                vis[j] = true;
                kol.push(j);
              }
            }
          }
          if (inny){
            has = true;
            break;
          }
        }
      }

      if (!has){
        res = 0;
      }
    }
/*
    printf("res %d\n", res);
    for(int i=0; i < n; i++){
      printf("%s\n", tab[i]);
    }
    printf("\n\n");*/
    tab[x][y] = '.';
    dodane.pop_back();
    return res;
  }
  ll res = 0ll;

  for(int j = y + 1; j < n; j++){
    if (tab[x][j] == '.')
      res += licz(x, j, zostalo-1);
  }

  for(int i = x + 1; i < n; i++){
    for(int j = 0; j < n; j++){
      if (tab[i][j] == '.'){
        res += licz(i, j, zostalo-1);
      }
    }
  }

  tab[x][y] = '.';
  dodane.pop_back();
  return res;
}

int main() {
  scanf("%d%d", &n, &k);
  for(int i = 0; i < n; i++) {
    scanf("%s", &tab[i]);
  }
  ll res = 0ll;
  for(int x = 0; x < n; x++) {
    for(int y = 0; y < n; y++) {
      if (tab[x][y] == '.'){
        res += licz(x, y, k);
        res %= P;
      }
    }
  }
  printf("%lld\n", res);
}