Busy Beaver 發現了一個奇怪的謎題。這個謎題由一個劃分為 $N \times M$ 格子的方盒組成。網格中的每個格子要麼是被佔用的（以 '#' 表示），要麼是空的（以 '.' 表示），或者是空的但標記為 'o'。

謎題附帶了一堆 L 型三格骨牌（L-tromino），網格中每個 'o' 格子對應一個。L 型三格骨牌由三個正方形塊組成，形狀如圖所示。L 型三格骨牌的中心是與其他兩個方塊相鄰的方塊（在圖中標記為 o）。

Busy Beaver 意識到要解決這個謎題，他需要將所有的 L 型三格骨牌放入盒子中，使得 L 型三格骨牌與網格對齊，每個 L 型三格骨牌的中心位於標記為 'o' 的空格子處，且沒有兩個 L 型三格骨牌重疊，也沒有 L 型三格骨牌與被佔用的格子重疊。所有的 L 型三格骨牌都可以自由旋轉。

你能幫助 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 型三格骨牌。