前置知识：矩阵树定理

如果不会请出门右转P6178 【模板】Matrix-Tree 定理。

我们考虑暴力，将每个点都扔到矩阵里面，那么复杂度为 $\mathcal O(n^3m^3)$。

考虑优化。可以发现，在不是空地的地方只有一种连边方式，那么我就直接考虑使用并查集缩点。由于这里会出现环的情况，直接强制规定比较小的为根。

在第一次编号跑完并查集之后，第二次重编号。注意判断连通块内如果没有空地，说明一定没有合法方案，直接输出 0。

那么一个连通块中至少有一个空地，所以行列式求值时间复杂度为 $\mathcal O(k^3)$，总时间复杂度就是 $\mathcal O(Tnm+Tk^3)$。

具体细节见代码（不过代码比较丑陋，见谅）。

:::info[code]

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<bitset>
#include<cstring>
#include<cctype>
#include<climits>
#include<queue>
using namespace std;
#define mod 1000000007
#define N 205
template<size_t Rows, size_t Cols>
inline long long gauss(int n,long long int (&p)[Rows][Cols]){
	if(n<1) return 1;
	int flag = 1;
	long long ans = 1;
	for(int k=1;k<=n;++k){
		for(int i=k+1;i<=n;++i){
			while(p[k][k]){
				long long t = p[i][k]/p[k][k];
				for(int j=k;t&&j<=n;++j){
					p[i][j]=(p[i][j]-t*p[k][j]%mod+mod)%mod;
				}
				swap(p[k],p[i]);
				flag*=-1;
			}
			swap(p[k],p[i]);
			flag*=-1;
		}
		ans = ans*p[k][k]%mod;
		if(!ans) return 0;
	}
	return (ans*flag+mod)%mod;
}
long long p[301][301];
int n,m,id[N][N],cnt = 0,fa[N*N];
pair<int,int> mp[N*N];
long long ans;
bitset<N> vis[N],indp[N];
bitset<N*N> lop;
inline void adde(int u,int v,int w=1){
	p[u][v]-=w;
	p[u][u]+=w;
	return ;
}
int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
inline bool merge(int x,int y){
	if((x=find(x))==(y=find(y))) return false;
	if(x>y) swap(x,y);
	fa[y] = x;
	return true; 
}
inline void work(){
	read(n,m);
	memset(p,0,sizeof p);
	lop.reset();
	
	mp[cnt = 1]=make_pair(0,0);
	for(int i=0;i<=n;++i) id[i][m+1] = id[i][0] = cnt;
	for(int i=0;i<=m;++i) id[0][i] = id[n+1][i] = cnt;
	for(int i=1;i<=n;++i){
		vis[i].reset();
		indp[i].reset();
		for(int j=1;j<=m;++j){
			id[i][j] = ++cnt;
			mp[cnt] = make_pair(i,j);
		}
	}
	
	for(int i=1;i<=cnt;++i) fa[i] = i;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			int op = gc();
			if(op=='L') merge(id[i][j],id[i][j-1]);
			else if(op=='R') merge(id[i][j],id[i][j+1]);
			else if(op=='U') merge(id[i][j],id[i-1][j]);
			else if(op=='D') merge(id[i][j],id[i+1][j]);
			else vis[i][j] = 1;
		}
	}
	
	cnt = 0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(id[i][j]==find(id[i][j])){
				id[i][j] = ++cnt;
				indp[i][j] = 1;
			}
		}
	}
	lop[++cnt] = 1;
	for(int i=0;i<=n;++i) id[i][m+1] = id[i][0] = cnt;
	for(int i=0;i<=m;++i) id[0][i] = id[n+1][i] = cnt;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(indp[i][j]) continue;
			id[i][j] = id[mp[find(id[i][j])].first][mp[find(id[i][j])].second];
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(vis[i][j]) lop[id[i][j]] = 1;
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(!vis[i][j]&&!lop[id[i][j]]){
				write("0\n");
				return ;
			}
		}
	}
	
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(!vis[i][j]) continue;
			adde(id[i][j],id[i][j+1]);
			adde(id[i][j],id[i][j-1]);
			adde(id[i][j],id[i-1][j]);
			adde(id[i][j],id[i+1][j]);
		}
	}
	write(gauss(cnt-1,p),'\n');
	return ;
}
int T;
int main(){
	cin>>T;
	while(T--) work();
	return 0;
}

:::