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
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <sstream>
#include <set>
#include <algorithm>
#include <deque>
using namespace std;

long n, m;
set<pair<long, long> > base;
set<pair<long, long> > base_ns;
set<set<pair<long, long> > > visited;
long result;
long MOD = 100000007;
pair<long, long> field;
set<pair<long, long> > fns;

void field_ns() {
  fns.clear();
  long x = field.first;
  long y = field.second;
  if (x - 1>=0) {
    fns.insert(make_pair(x-1, y));
  }
  if (y-1 >= 0) {
    fns.insert(make_pair(x, y-1));
  }
  if (x + 1 < n) {
    fns.insert(make_pair(x+1, y));
  }
  if (y + 1 < n) {
    fns.insert(make_pair(x, y+1));
  }
}

void print_pos(set<pair<long, long> > pos) {
  cout << "[";
  for (set<pair<long, long> >::iterator it=pos.begin(); it!=pos.end(); it++) {
    cout << "(" << it->first << "," << it->second << "),";
  }
  cout << "]";
  cout << endl;
}

void init_base_ns() {
  long count = 0;
  for (set<pair<long, long> >::iterator it=base.begin(); it!=base.end(); it++) {
    field = *it;
    field_ns();
    for (set<pair<long, long> >::iterator jt = fns.begin(); jt!=fns.end(); jt++) {
      if (base.find(*jt) == base.end()) {
        base_ns.insert(*jt);
      }
    }
  }
}

int main() {
  scanf("%ld %ld\n", &n, &m);
  for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
      char c;
      if (j == n-1) {
        scanf("%c\n", &c);
      } else {
        scanf("%c", &c);
      }
      if (c == '#') {
        pair<long, long> coord = make_pair(i,j);
        base.insert(coord);
      }
    }
  }
 // cout << "before init" << endl << flush;
  init_base_ns();
  //cout << "after init" << endl << flush;
//  print_pos(base_ns);
  set<pair<long, long> > s0;
  deque<set<pair<long, long> > > que;
  que.push_back(s0);
  while (!que.empty()) {
    set<pair<long, long> > current = que.front();
    que.pop_front();
    visited.insert(current);
    // cout << "current: ";
    // print_pos(current);
    long size = current.size();
    if (size == m) {
      result = (result + 1) % MOD;
    } else if (size < m) {
      for (set<pair<long, long> >::iterator it=current.begin(); it!=current.end(); it++) {
        field = *it;
        field_ns();
        for (set<pair<long, long> >::iterator jt = fns.begin(); jt!=fns.end(); jt++) {
          if (base.find(*jt) == base.end() && current.find(*jt) == current.end()) {
            set<pair<long, long> > pose(current);
            pose.insert(*jt);
            if (visited.find(pose) == visited.end()) {
              que.push_back(pose);
              visited.insert(pose);
            }
          }
        }
      }
      for (set<pair<long, long> >::iterator it=base_ns.begin(); it!=base_ns.end(); it++) {
        if (current.find(*it) == current.end()) {
          set<pair<long, long> > pose(current);
          pose.insert(*it);
          if (visited.find(pose) == visited.end()) {
            que.push_back(pose);
            visited.insert(pose);
          }
        }
      }
    }
  }
  cout << result << endl;
  return 0;
}