#6259. 「CodePlus 2017 12 月赛」白金元首与独舞

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cyand1317

题目描述

到河北省 见斯大林 / 在月光下 你的背影 / 让我们一起跳舞吧

うそだよ~ 河北省怎么可能有 Stalin。

可是…… 可是如果 Stalin 把自己当作炸弹扔到地堡花园里来了呢?

怀揣着这份小小的希望,元首 Adolf 独自走进了花园。终有一天会重逢的吧,Stalin。或许是在此处,或许是在遥远的彼方。

无论如何,在此之前,好好装点一番花园,编排一段优美的舞步吧!


元首把花园分为 nnmm 列的网格。每个格子中都可以放置一个标识,指向上、下、左、右四个方向中的任意一个。元首位于一个格子时,会按照其中标识所指的方向进入周围的格子,或者走出花园(即目的格子不在网格之内)。举个例子 —— 对于下面的放置方式,元首从第 33 行第 22 列的格子开始,会沿着以红色标出的路径走出花园;从第 22 行第 22 列的格子开始,则会在以蓝色标出的环路内不断地行走。

←  

←  

  ↑

  ←

元首已经设计好了大部分格子的标识。元首用字符 LRUD 分别表示指向左、右、上、下四个方向的标识,用字符 . 表示未决定的格子。现在,元首希望将每个 . 替换为 LRUD 中任意一种,使得从花园中的任意一个格子出发,按照上述规则行走,都可以最终走出花园。

你需要编写程序帮助元首计算替换的不同方案数。两个方案不同当且仅当存在一个格子,使得两个方案中该格子内的标识不同。当然,由于答案可能很大,只需给出方案数除以 109+710^9 + 7 所得的余数即可。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 TT —— 测试数据的组数。接下来包含 TT 组测试数据,格式如下,测试数据间没有空行。

  • 11 行:两个空格分隔的正整数 nnmm —— 依次表示花园被分成的行数和列数。
  • 接下来 nn 行:每行一个长度为 mm 的由字符 LRUD. 组成的字符串 —— 表示花园内已经确定的格子状态。

输出格式

输出到标准输出。

对于每组测试数据输出一行 —— 满足条件的方案数除以 109+710^9 + 7 所得的余数。

样例

样例输入

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
..
..

样例输出

3
8
0
1
192

样例解释

11 组数据中,将惟一的 . 替换成 RUD 均满足要求。

22 组数据中,将左上方和右下方的两个 . 分别替换成 LRLULDURUUUDDRDD 均满足要求。

33 组数据中,没有待决定的格子,原本的安排会使得元首陷入无尽的环路,故答案为 00。该组数据与【题目描述】中的例子相同。

44 组数据中,也没有待决定的格子,但原本的安排已经满足要求,故答案为 11

数据范围与提示

kk 表示标记未确定(即包含 “.”)的格子总数。

对于所有数据,有 1T101 \leq T \leq 101n,m2001 \leq n, m \leq 2000kmin(nm,300)0 \leq k \leq \min(nm, 300)

测试点编号nn, mm kk 特殊约定
150\leq 50 =0= 0
2200\leq 200
32\leq 2 4\leq 4
44\leq 4 7\leq 7
510\leq 10
6
7100\leq 100
8
9
10
11200\leq 200 200\leq 200 n=1n = 1
12
13有且仅有第 11 行的所有格子中标记未确定
14
15
16300\leq 300
17
18
19
20

... wie Stalin!

题面与史实无关。


来自 CodePlus 2017 12 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea/吕时清 命题/吕时清 验题/王聿中,杨景钦
Git Repo:https://git.thusaac.org/publish/CodePlus201712
感谢腾讯公司对此次比赛的支持。