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
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define dd second
#define mp make_pair
#define lld long long
#define sz size()
#define pb push_back
#define For(i,s,a) for(lld i=(lld)s;i<(lld)a;++i)
#define gecx() getchar()
#define pii pair<int,int>
#define piii pair<pair<pii ,pii >,pair<pii ,pii > >
template<typename T>
void scan(T &i)
{
	 T tt;
	 char cc;
	 tt=0;
	 cc='a';
	 bool neg=0;
	 while(cc>'9' || cc<'0')
	 {
		   if(cc=='-')
		   neg=1;
		   cc=gecx();
	 }
	 while(cc>='0' && cc<='9')
	 {
		   tt=(tt<<3ll)+(tt<<1ll)+cc-'0';
		   cc=gecx();
	 }
	 *i=tt;
}

bitset<3001>odw[3001];
char s[3001];
map<set<pii>,int>c;
lld wyn;
int x,y;
/*
void dfs(int a, int b, set<pii> xd, int k)
{
	if(a>x || b>y)return;
	cout<<a<<" "<<b<<" "<<k<<endl;
	if(!k){++wyn;return;}	c[xd]=1;
	odw[a][b]=1;
		xd.insert(mp(a+1,b));
		if(!c[xd] && x>a+1 && !odw[a+1][b])
		dfs(a+1,b,xd,k-1);
		xd.insert(mp(a-1,b));
		if(!c[xd] && a && !odw[a-1][b])
		dfs(a-1,b,xd,k-1);
		xd.insert(=mp(a,b+1));
		if(!c[xd] && b<y-1 && !odw[a][b+1])
		dfs(a,b+1,xd,k-1);
		xd.insert(mp(a,b-1));
		if(!c[xd] && b && !odw[a][b-1])
		dfs(a,b-1,xd,k-1);
		
	odw[a][b]=0;
}
*/

bool chk(int a, int b)
{
	if(a && odw[a-1][b])return 1;
	else
	if(a<x-1 && odw[a+1][b])return 1;
	else
	if(b && odw[a][b-1])return 1;
	else
	if(b<x-1 && odw[a][b+1])return 1;
	else
	return 0;	
}

void bfs(set<pii> xd,int k)
{
//	cout<<k<<endl;
	if(!k){++wyn;return;}
	For(i,0,x)
	For(j,0,x)
	{
	//	cout<<i<<" "<<j<<" "<<k<<endl;
		if(!odw[i][j] && chk(i,j))
		{
			odw[i][j]=1;
			xd.insert(mp(i,j));
			if(!c[xd]){
			c[xd]=1;
			bfs(xd,k-1);}
			odw[i][j]=0;
			xd.erase(xd.find(mp(i,j)));
		}
	}
}

int main()
{
	scanf("%d%d", &x,&y);
	For(i,0,x)
	{
		scanf("%s",s);
		For(j,0,x)
		if(s[j]=='#')
		odw[i][j]=1;
	}
	set<pii> xd;
	xd.insert(mp(-1,-1));
	bfs(xd,y);
	printf("%lld",wyn);
}