Description

The Führer divides the garden into an $n$ by $m$ grid. Each cell can hold a marker pointing in one of the four directions: up, down, left, or right. When the Führer is in a cell, he moves to the adjacent cell indicated by the marker, or leaves the garden if the target cell is outside the grid. For example — in the placement below, starting from the cell at row $3$, column $2$, the Führer will leave the garden along the red path; starting from row $2$, column $2$, he will keep walking around the blue cycle.

Most cells’ markers have already been designed. Characters L, R, U, D denote markers pointing left, right, up, and down, respectively, and the character . denotes an undecided cell. Now, the Führer wants to replace each . with one of L, R, U, D so that starting from any cell in the garden and following the rule above, the walk will eventually leave the garden.

You need to write a program to count the number of different valid replacements. Two replacements are different if and only if there exists a cell whose marker differs between the two. Since the answer can be large, output the remainder modulo $10^9 + 7$.

Input Format

Read from standard input.

The first line contains a positive integer $T$ — the number of test cases. Then follow $T$ test cases with no blank lines between them.

Line 1: Two space-separated positive integers $n$, $m$ — the number of rows and columns of the garden.

Next $n$ lines: Each line is a string of length $m$ consisting of characters L, R, U, D, and . — the current state of the garden.

Output Format

Output to standard output.

For each test case, output one line — the number of valid replacements modulo $10^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

Hint

Sample explanation.

In the first test, replacing the only . with R, U, or D all works.

In the second test, the two . at the top-left and bottom-right can be replaced, respectively, as one of the pairs LR, LU, LD, UR, UU, UD, DR, or DD.

In the third test, there is no undecided cell, and the original arrangement traps the Führer in an endless cycle, so the answer is $0$. This test matches the example in the Description.

In the fourth test, there is also no undecided cell, and the original arrangement already satisfies the requirement, so the answer is $1$.

Let $k$ be the total number of undecided cells (those containing .).

For all test cases, $1 \le T \le 10$, $1 \le n, m \le 200$, $0 \le k \le \min(nm, 300)$.

“... like Stalin.”

This problem statement is unrelated to historical facts.

From CodePlus December 2017 Contest, proudly presented by the Student Association for Algorithms and Competitions, Department of Computer Science and Technology, Tsinghua University.

Credit: idea/吕时清, problem setting/吕时清, verification/王聿中, 杨景钦.

Git Repo: https://git.thusaac.org/publish/CodePlus201712

Thanks to Tencent for supporting this contest.

Translated by ChatGPT 5