你想要打通一些相邻房间的墙，使得所有房间能够互相到达。在此过程中，你不能把房子给打穿，或者打通柱子（以及柱子旁边的墙）。同时，你不希望在房子中有小偷的时候会很难抓，所以你希望任意两个房间之间都只有一条通路。现在，你希望统计一共有多少种可行的方案。

接下来n行，每行m个字符，每个字符都会是’.’或者’*’，其中’.’代表房间，’*’代表柱子。

#include <cmath>

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long ll;

const int mod = 1000000000;

int dx[] = {1 , 0 , -1 , 0} , dy[] = {0 , 1 , 0 , -1} , pos[15][15] , tot;

ll a[110][110];

char str[15];

int main()

{

	int n , m , i , j , k , d = 0 , t;

	ll ans = 1;

	scanf("%d%d" , &n , &m);

	for(i = 1 ; i <= n ; i ++ )

	{

		scanf("%s" , str + 1);

		for(j = 1 ; j <= m ; j ++ )

			if(str[j] == '.')

				pos[i][j] = ++tot;

	}

	for(i = 1 ; i <= n ; i ++ )

		for(j = 1 ; j <= m ; j ++ )

			if(pos[i][j])

				for(k = 0 ; k < 4 ; k ++ )

					if(pos[i + dx[k]][j + dy[k]])

						a[pos[i][j]][pos[i][j]] ++ , a[pos[i][j]][pos[i + dx[k]][j + dy[k]]] -- ;

	for(i = 1 ; i < tot ; i ++ )

	{

		for(j = i ; j < tot ; j ++ )

			if(a[j][i])

				break;

		if(j == tot) continue;

		if(j != i)

		{

			for(k = i ; k < tot ; k ++ ) swap(a[i][k] , a[j][k]);

			d ^= 1;

		}

		for(j = i + 1 ; j < tot ; j ++ )

		{

			while(a[j][i])

			{

				t = a[j][i] / a[i][i];

				for(k = i ; k < tot ; k ++ ) a[j][k] = (a[j][k] - a[i][k] * t % mod + mod) % mod;

				if(!a[j][i]) break;

				for(k = i ; k < tot ; k ++ ) swap(a[i][k] , a[j][k]);

				d ^= 1;

			}

		}

	}

	for(i = 1 ; i < tot ; i ++ ) ans = ans * a[i][i] % mod;

	if(d) ans = (mod - ans) % mod;

	printf("%lld\n" , ans);

	return 0;

}