白金元首与独舞（矩阵树定理）

//这道题是矩阵树定理中：给出有向图和其中一个点，求以这个点为根的生成外向树个数
/*
 矩阵树定理：有向图有根树的情况
 去掉所有自环，主对角线上第i行第i列是i这个点的出度，剩下的是邻接矩阵取相反数。
 然后求的是删掉根节点所在行列式的余子式的行列式
 */

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
typedef long long ll;
using namespace std;

#define maxr 210
#define maxnode 40010
#define maxn 310
#define MOD 1000000007
#define LL long long

int T, r, c;
char Map[maxr][maxr]; //记录r行c列的字符

struct Graph //Graph有clear 和 AddEdge函数
{
    int n, m;
    int head[maxnode], nxt[maxnode], to[maxnode];
    Graph() {}

    void clear() //一开始的m为0（0条边），head都是0
    {
        m = 0;
        memset(head, 0, sizeof(head));
        return ;
    }

    void AddEdge(int a, int b) //添加边
    {
        //第++m条边，
        ++m;
        to[m] = b;         //第m条边的to是b
        nxt[m] = head[a];  //第m条边的nxt是head[a] -> 之后head[a]=m
        head[a] = m;       //a的head是m
        return ;
    }
} G;

int id(int i, int j)
{
    return (i - 1) * c + j;
}
int vis[40010];

bool dfs(int u)
{
    if(vis[u] == 2) return 0;
    if(vis[u]) return 1;
    vis[u] = 2;
    for(int e = G.head[u]; e; e = G.nxt[e])
    {
        if(dfs(G.to[e])==0)
        {
            return 0;
        }
    }
    vis[u] = 1;
    return 1;
}

int pre[40010]; //祖先函数（pre)

int find(int x)  //寻找x的祖先(并查集)
{
    if(x==pre[x]) return x;
    else return pre[x]=find(pre[x]);
}

int n, trid[40010];

int ID(int u)
{
    if(trid[u]!=0) return trid[u];
    else return trid[u]=++n;
}

int A[maxn][maxn], tA[maxn][maxn];

void MatAddEdge(int a, int b)
{
    if(a == b) return ;
    tA[a][a]++; tA[a][b]--;
    return ;
}

void elim(int *a, int *b, int tar)
{
    if(!b[tar]) return ;
    int rate = a[tar] / b[tar];
    for (int i=1;i<=n;i++)
    {
        a[i] = ((LL)a[i] - (LL)b[i] * rate % MOD + MOD) % MOD;
    }
    elim(b, a, tar);
    return ;
}

int solve()
{
    n--;
    int sgn = 1;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if(A[i][j] < 0) A[i][j] += MOD;
        }
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=i+1;j<=n;j++)
        {
            if(A[j][i])
            {
                elim(A[i], A[j], i);
                if(!A[i][i])
                {
                    swap(A[i], A[j]);
                    sgn = -sgn;
                }
            }
        }
    }
    int sum = 1;
    for (int i=1;i<=n;i++)
    {
        sum = (LL)sum * A[i][i] % MOD;
    }
    return (sum * sgn + MOD) % MOD;
}

int main()
{
    cin >> T; //多少组样例
    while(T--)
    {
        cin >> r >> c; //r代表行数，c代表列数
        G.n = r * c + 1; //图表里面的 n=行数*列数+1

        /*初始化*/
        G.clear();
        for (int i=1;i<=G.n;i++) //每一个点的祖先都是自己
        {
            pre[i]=i;
        }
        /*进行图的更新*/
        for (int i=1;i<=r;i++) //输入r行，一行一个字符串
        {
            scanf("%s", Map[i] + 1); //想要以这种方法输入，必须是char数组的形式，不能是string的形式
        }
        for (int i=1;i<=r;i++) //遍历一共r行
        {
            for (int j=1;j<=c;j++) //遍历一共j行
            {
                if(Map[i][j] == 'D')//如果i不是最后一行，则D可以进行，否则就出去了
                {
                    int x=id(i,j);
                    int y;
                    if(i!=r) y=id(i+1,j);
                    else y=G.n;
                    G.AddEdge(x, y);
                    int u = find(x);
                    int v = find(y);
                    if(u != v) pre[v] = u;   //如果两者的祖先不相同，就进行合并
                }
                if(Map[i][j] == 'U')
                {
                    int x=id(i,j);
                    int y;
                    if(i!=1) y=id(i-1,j);
                    else y=G.n;
                    G.AddEdge(x, y);
                    int u=find(x);
                    int v=find(y);
                    if(u!=v) pre[v]=u;
                }
                if(Map[i][j] == 'R')
                {
                    G.AddEdge(id(i, j), j < c ? id(i, j + 1) : G.n);
                    int u = find(id(i, j)), v = find(j < c ? id(i, j + 1) : G.n);
                    if(u != v) pre[v] = u;
                }
                if(Map[i][j] == 'L')
                {
                    G.AddEdge(id(i, j), j > 1 ? id(i, j - 1) : G.n);
                    int u = find(id(i, j)), v = find(j > 1 ? id(i, j - 1) : G.n);
                    if(u != v) pre[v] = u;
                }
            }
        }
        memset(vis, 0, sizeof(vis));     //初始化vis函数
        bool ok = 1;

        for(int i=1;i<=G.n;i++)
        {
            if(vis[i]==0 && dfs(i)==0)
            {
                cout << "0" << endl;
                ok = 0;
                break;
            }
        }

        if(!ok) continue;

        memset(trid, 0, sizeof(trid)); n = 0;
        memset(tA, 0, sizeof(tA));
        for (int i=1;i<=r;i++)
        {
            for (int j=1;j<=c;j++)
            {
                if(Map[i][j]=='.')
                {
                    int u = find(id(i, j));
                    MatAddEdge(ID(u), ID(find(i < r ? id(i + 1, j) : G.n)));
                    MatAddEdge(ID(u), ID(find(i > 1 ? id(i - 1, j) : G.n)));
                    MatAddEdge(ID(u), ID(find(j < c ? id(i, j + 1) : G.n)));
                    MatAddEdge(ID(u), ID(find(j > 1 ? id(i, j - 1) : G.n)));
                }
            }
        }

        int ci = 0, cj = 0;
        for (int i=1;i<=n;i++)
        {
            if(i != ID(find(G.n)))
            {
                ci++;
                cj = 0;
                for (int j=1;j<=n;j++)
                {
                    if(j != ID(find(G.n)))
                    {
                        A[ci][++cj] = tA[i][j];
                    }
                }
            }
        }
        cout << solve() << endl;
    }
    return 0;
}