A2504. 白金元首与独舞
编程题
省选/NOI-
知识点
题目描述
```cpp
到河北省 见斯大林 / 在月光下 你的背影 / 让我们一起跳舞吧
```
うそだよ~ 河北省怎么可能有 Stalin。
可是…… 可是如果 Stalin 把自己当作炸弹扔到地堡花园里来了呢？
怀揣着这份小小的希望，元首 Adolf 独自走进了花园。终有一天会重逢的吧，Stalin。或许是在此处，或许是在遥远的彼方。
无论如何，在此之前，好好装点一番花园，编排一段优美的舞步吧！
元首把花园分为 $n$ 行 $m$ 列的网格。每个格子中都可以放置一个标识，指向上、下、左、右四个方向中的任意一个。元首位于一个格子时，会按照其中标识所指的方向进入周围的格子，或者走出花园（即目的格子不在网格之内）。举个例子 —— 对于下面的放置方式，元首从第 $3$ 行第 $2$ 列的格子开始，会沿着以红色标出的路径走出花园；从第 $2$ 行第 22 列的格子开始，则会在以蓝色标出的环路内不断地行走。
元首已经设计好了大部分格子的标识。元首用字符 L、R、U、D 分别表示指向左、右、上、下四个方向的标识，用字符 . 表示未决定的格子。现在，元首希望将每个 . 替换为 L、R、U、D 中任意一种，使得从花园中的任意一个格子出发，按照上述规则行走，都可以最终走出花园。
你需要编写程序帮助元首计算替换的不同方案数。两个方案不同当且仅当存在一个格子，使得两个方案中该格子内的标识不同。当然，由于答案可能很大，只需给出方案数除以 $10^9 + 7$所得的余数即可。
到河北省 见斯大林 / 在月光下 你的背影 / 让我们一起跳舞吧
```
うそだよ~ 河北省怎么可能有 Stalin。
可是…… 可是如果 Stalin 把自己当作炸弹扔到地堡花园里来了呢？
怀揣着这份小小的希望，元首 Adolf 独自走进了花园。终有一天会重逢的吧，Stalin。或许是在此处，或许是在遥远的彼方。
无论如何，在此之前，好好装点一番花园，编排一段优美的舞步吧！
元首把花园分为 $n$ 行 $m$ 列的网格。每个格子中都可以放置一个标识，指向上、下、左、右四个方向中的任意一个。元首位于一个格子时，会按照其中标识所指的方向进入周围的格子，或者走出花园（即目的格子不在网格之内）。举个例子 —— 对于下面的放置方式，元首从第 $3$ 行第 $2$ 列的格子开始，会沿着以红色标出的路径走出花园；从第 $2$ 行第 22 列的格子开始，则会在以蓝色标出的环路内不断地行走。
元首已经设计好了大部分格子的标识。元首用字符 L、R、U、D 分别表示指向左、右、上、下四个方向的标识，用字符 . 表示未决定的格子。现在，元首希望将每个 . 替换为 L、R、U、D 中任意一种，使得从花园中的任意一个格子出发，按照上述规则行走，都可以最终走出花园。
你需要编写程序帮助元首计算替换的不同方案数。两个方案不同当且仅当存在一个格子，使得两个方案中该格子内的标识不同。当然，由于答案可能很大，只需给出方案数除以 $10^9 + 7$所得的余数即可。
输入格式
从标准输入读入数据。
输入的第一行包含一个正整数 $T$ —— 测试数据的组数。接下来包含 $T$ 组测试数据，格式如下，测试数据间没有空行。
第 $1$ 行：两个空格分隔的正整数 $n$、$m$ —— 依次表示花园被分成的行数和列数。
接下来 $n$ 行：每行一个长度为 $m$ 的由字符 L、R、U、D 和 . 组成的字符串 —— 表示花园内已经确定的格子状态。
输入的第一行包含一个正整数 $T$ —— 测试数据的组数。接下来包含 $T$ 组测试数据，格式如下，测试数据间没有空行。
第 $1$ 行：两个空格分隔的正整数 $n$、$m$ —— 依次表示花园被分成的行数和列数。
接下来 $n$ 行：每行一个长度为 $m$ 的由字符 L、R、U、D 和 . 组成的字符串 —— 表示花园内已经确定的格子状态。
输出格式
输出到标准输出。
对于每组测试数据输出一行 —— 满足条件的方案数除以 $10^9 + 7$所得的余数。
对于每组测试数据输出一行 —— 满足条件的方案数除以 $10^9 + 7$所得的余数。
输入输出样例
输入 #1
5 3 9 LLRRUDUUU LLR.UDUUU LLRRUDUUU 4 4 LLRR L.LL RR.R LLRR 4 3 LRD LUL DLU RDL 1 2 LR 2 2 .. ..
输出 #1
3 8 0 1 192
说明/提示
**样例解释**
第 $1$ 组数据中，将惟一的 . 替换成 R、U 或 D 均满足要求。
第 $2$ 组数据中，将左上方和右下方的两个 . 分别替换成 LR、LU、LD、UR、UU、UD、DR 或 DD 均满足要求。
第 $3$ 组数据中，没有待决定的格子，原本的安排会使得元首陷入无尽的环路，故答案为 $0$。该组数据与**题目描述**中的例子相同。
第 $4$ 组数据中，也没有待决定的格子，但原本的安排已经满足要求，故答案为 $1$。
令 $k$ 表示标记未确定（即包含 “.”）的格子总数。
对于所有数据，有 $1 \leq T \leq 10$，$1 \leq n, m \leq 200$，$0 \leq k \leq \min(nm, 300)$。
第 $1$ 组数据中，将惟一的 . 替换成 R、U 或 D 均满足要求。
第 $2$ 组数据中，将左上方和右下方的两个 . 分别替换成 LR、LU、LD、UR、UU、UD、DR 或 DD 均满足要求。
第 $3$ 组数据中，没有待决定的格子，原本的安排会使得元首陷入无尽的环路，故答案为 $0$。该组数据与**题目描述**中的例子相同。
第 $4$ 组数据中，也没有待决定的格子，但原本的安排已经满足要求，故答案为 $1$。
令 $k$ 表示标记未确定（即包含 “.”）的格子总数。
对于所有数据，有 $1 \leq T \leq 10$，$1 \leq n, m \leq 200$，$0 \leq k \leq \min(nm, 300)$。