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
// Carcassonne.cpp : Defines the entry point for the console application.       
//                                                                              

//#include "stdafx.h"                                                           

#include <cassert>                                                              
#include <iostream>                                                             
#include <istream>                                                              
#include <fstream>                                                              
#include <algorithm>                                                            
#include <cstdio>                                                               
#include <complex>                                                              
#include <vector>                                                               
#include <set>                                                                  
#include <map>                                                                  
#include <cmath>                                                                
#include <queue>                                                                
#include <string>                                                               
#include <cstdlib>                                                              
#include <memory>                                                               
#include <ctime>                                                                
#include <bitset>                                                               
#include <queue>                                                                
#include <stack>                                                                
#include <unordered_map>                                                        
#include <unordered_set>                                                        
#include <bitset>                                                               
using namespace std;

const long long MOD = 1e9 + 7;
const char CHAR0 = '.';
const char CHAR1 = '#';
long long result = 0;

int n;
int k;

string stab;

unordered_set<string> solutions;

struct pairhash {
public:
	template <typename T, typename U>
	std::size_t operator()(const std::pair<T, U> &x) const
	{
		return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
	}
};

void read() {

	cin >> n >> k;
	string str;
	for (int i = 0; i < n; i++) {
		cin >> str;
		stab += str;
	}
}
unordered_map< pair<int, int>, int, pairhash > possiblePlaces(string game) {

	unordered_map< pair<int, int>, int, pairhash > map;

	for (int i = 0; i < n; i++) {

		for (int j = 0; j < n; j++) {
			if (game[i * n + j] == CHAR0) {
				if ((i > 0 && game[(i - 1) * n + j] == CHAR1) || (i < n - 1 && game[(i + 1) * n + j] == CHAR1) || (j > 0 && game[i * n + j - 1] == CHAR1) || (j
						< n - 1 && game[i * n + j + 1] == CHAR1))
				{
					map.emplace(make_pair(i, j), 1);
				}
			}
		}
	}
	return map;
}

string sgetNext(string& game, pair<int, int> p) {
	string next(game);
	next[p.first * n + p.second] = CHAR1;
	return next;
}

void solve(string game, int level) {
	if (level == k) {
		solutions.insert(game);
	}
	else {
		for (auto place : possiblePlaces(game)) {
			solve(sgetNext(game, place.first), level + 1);
		}
	}
}

int main() {

	read();

	solve(stab, 0);
	result = solutions.size() % MOD;
	cout << result << endl;
	return 0;
}