Busy Beaver 发现了一个奇怪的谜题。谜题由一个划分为 $N \times M$ 网格的盒子组成。网格中的每个单元格要么是被占用的（用 '#' 表示），要么是空的（用 '.' 表示），或者是空的但标记为 'o'。

谜题附带了一堆 L-tromino 拼图块，网格中每个 'o' 单元格对应一个。L-tromino 由三个正方形块组成，形状呈 L 型，如图所示。L-tromino 的中心是与另外两个正方形都相邻的那个方块（在图中标记为 o）。

Busy Beaver 意识到，要解决这个谜题，他需要将所有的 L-tromino 放入盒子中，使得 L-tromino 与网格对齐，每个 L-tromino 的中心位于标记为 'o' 的空单元格上，且没有两个 L-tromino 相互重叠，也没有 L-tromino 与被占用的单元格重叠。所有的 L-tromino 都可以自由旋转。

你能帮助 Busy Beaver 计算出解决该谜题的方法数吗？由于答案可能很大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $T$ ($1 \le T \le 500$)。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $N$ 和 $M$ ($2 \le N, M \le 1000$)，表示网格的尺寸。

接下来的 $N$ 行，每行包含 $M$ 个字符，描述网格的一行。每个字符要么是 '#'，'.'，要么是 'o'。

保证所有测试用例的 $N$ 之和不超过 1000。 保证所有测试用例的 $M$ 之和不超过 1000。

输出格式

对于每个测试用例，输出一个整数：解决该谜题的方法数，对 $10^9 + 7$ 取模。

子任务

令 $(r, c)$ 表示第 $r$ 行第 $c$ 列的单元格 ($1 \le r \le N, 1 \le c \le M$)。

• (10 分) 每个 'o' 单元格与其他 'o' 单元格的曼哈顿距离至少为 3。即，如果 $(r_1, c_1)$ 和 $(r_2, c_2)$ 是两个不同的 'o' 单元格，则 $|r_1 - r_2| + |c_1 - c_2| \ge 3$。
• (30 分) 每个 'o' 单元格在垂直方向上至少与另一个 'o' 或 '#' 单元格相邻。即，对于任何位于 $(r, c)$ 的 'o' 单元格，$(r - 1, c)$ 或 $(r + 1, c)$ 必须是 '#' 单元格或另一个 'o' 单元格。
• (60 分) 无额外限制。

样例

输入 1

5
4 5
###.o
.o...
#..o.
#..##
5 5
..###
.o..#
.o.o.
..#o.
###..
8 31
.########.#..oo..o..o#o..o....o
o.######.o#o...o..o..#..o..oo..
o..####.o.#####..########o..###
..o.o..o..#####.o########..o###
.o##..##.o#####o.########..o###
o.##.o##.o#####..########o..###
..######..#..o..o.o..####..o###
.o######o.#o..o..o..o####o..###
2 3
#.o
.o.
2 2
..
..

输出 1

4
6
1
0
1

说明

注意，第一个测试用例满足第一个子任务的约束，第二个测试用例满足第二个子任务的约束。

在第一个测试用例中，解决谜题的 4 种方法如图所示：

在第二个测试用例中，解决谜题的 6 种方法如图所示：

在第三个测试用例中，解决谜题的唯一方法如图所示：

在第四个测试用例中，没有解决谜题的方法。

在第五个测试用例中，没有 'o' 单元格，因此解决谜题的唯一方法是不放置任何 L-tromino。