矩阵树裸题
直接暴力把基尔霍夫矩阵给跑出来，去掉最后一行和最后一列求主子式即可
//minamoto
#include<bits/stdc++.h>
#define rint register int
using namespace std;
const int N=105,P=1e9;
int n,m,tot,f[N][N],mp[N][N];
inline void add(int u,int v){++f[u][u],++f[v][v],--f[u][v],--f[v][u];}
int Gauss(){
int ans=1;
for(rint i=1;i<tot;++i){
for(rint j=i+1;j<tot;++j)while(f[j][i]){
int t=f[i][i]/f[j][i];
for(rint k=i;k<tot;++k)
f[i][k]=(f[i][k]-1ll*t*f[j][k]+P)%P;
for(rint k=i;k<tot;++k)swap(f[i][k],f[j][k]);
ans=-ans;
}
ans=1ll*ans*f[i][i]%P;
}
return ans<0?ans+P:ans;
}
char s[N];int u,v;
int main(){
scanf("%d%d",&n,&m);
for(rint i=1;i<=n;++i){
scanf("%s",s+1);for(rint j=1;j<=m;++j)if(s[j]=='.')mp[i][j]=++tot;
}
for(rint i=1;i<=n;++i)for(rint j=1;j<=m;++j){
if(!(u=mp[i][j]))continue;
if(v=mp[i+1][j])add(u,v);
if(v=mp[i][j+1])add(u,v);
}
printf("%d
",Gauss());return 0;
}