这题要求解生成树的个数，应该使用 Matrix-Tree 定理。

如果使用高斯消元解行列，那么会出现除法。所以我们应该使用欧几里得算法。

具体来分析高斯消元，高斯消元时进行初等变换，把某行乘一个数字 $x$ 在加到另一行，最终使目标行某个位置为 $0$。

我们可以设对应位置数值为 $a$， $b$ 使得 $b = 0$。则使 $b$ 所在行 $+a$ 所在行 $\times b \div a$ 使得 $a$， $b \bmod a$ 交换，直到 $a$， $b$ 中出现 $0$ 为止。

AC代码

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 10;
const int INF = 0x3f;
int n, m, S, mod = 1000000000;
int s[11][11], a[82][82];
char z[11][11];
int gs(){
	S--; 
	for(int i = 1;i <= S; i++){
		for(int j = 1;j <= S; j++){
			a[i][j] = (a[i][j] + mod) % mod;
		}
	} 
	long long ans = 1;
	for(int j = 1;j <= S; j++){
		for(int i = j + 1;i <= S; i++)
		while(a[i][j]){
			LL t = a[j][j] / a[i][j];
			for(int k = j;k <= S; k++)
				a[j][k] = (a[j][k] - t * a[i][k] % mod + mod) % mod,
				swap(a[i][k] ,a[j][k]);
			ans *= -1;
		}
		ans = ans * a[j][j] % mod;
	}
	return (ans + mod) % mod;
} 
int main()
{
	cin >> n >> m;
	for(int i = 1;i <= n; i++){
		scanf("%s", &z[i][1]);
	}
	for(int i = 0;i <= n + 1; i++){
		for(int j = 0;j <= m + 1; j++){
			if(i == 0 || j == 0 || i == n + 1 || j ==m + 1)
				z[i][j] = '*';
		}
	}
	for(int i = 1;i <= n; i++){
		for(int j = 1;j <= m; j++){
			if(z[i][j] == '.'){
				s[i][j] = ++S;
				if(z[i - 1][j] == '.')a[s[i-1][j]][s[i][j]] = 1;
				if(z[i - 1][j] == '.')a[s[i][j]][s[i-1][j]] = 1;
				if(z[i][j - 1] == '.')a[s[i][j-1]][s[i][j]] = 1;
				if(z[i][j - 1] == '.')a[s[i][j]][s[i][j-1]] = 1;
			}
		}
	}
	for(int i = 1;i <= S;i++){
		for(int j = 1;j <= S; j++){
			if(a[i][j] && i!= j)a[i][i] ++;
		}
	}
	cout << gs();
    return 0;
}