Busy Beaver は奇妙なパズルを見つけました。このパズルは、$N \times M$ のマス目に分割された箱で構成されています。グリッドの各セルは、占有されている（'#' で表される）、空である（'.' で表される）、または空だが 'o' でマークされている、のいずれかです。

このパズルには、グリッドの各 'o' セルに対して1つずつ、L-トロミノのピースが付属しています。L-トロミノは、図のように L 字型に並んだ3つの正方形ブロックで構成されています。L-トロミノの中心とは、他の2つの正方形の両方に隣接している正方形のことです（図では 'o' でマークされています）。

Busy Beaver は、パズルを解くためには、すべての L-トロミノを箱の中に詰め込む必要があることに気づきました。その際、L-トロミノはグリッドに合わせて配置し、各 L-トロミノの中心は 'o' でマークされた空のセルになければならず、どの2つの L-トロミノも互いに重なったり、占有されたセルと重なったりしてはいけません。すべての L-トロミノは自由に回転させることができます。

Busy Beaver がパズルを解く方法の数を数えるのを手伝ってください。答えは大きくなる可能性があるため、$10^9 + 7$ で割った余りを出力してください。

入力

各テストケースには複数のテストケースが含まれます。最初の行にはテストケースの数 $T$ ($1 \le T \le 500$) が含まれます。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、グリッドの次元を表す2つの整数 $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)$ が異なる2つの 'o' セルである場合、$|r_1 - r_2| + |c_1 - c_2| \ge 3$ です。
• (30点) 各 'o' セルは、少なくとも1つの他の 'o' セルまたは '#' セルと垂直に隣接しています。つまり、任意の 'o' セル $(r, c)$ に対して、$(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

注記

最初のテストケースは最初の小課題の制約を満たし、2番目のテストケースは2番目の小課題の制約を満たしています。

最初のテストケースにおけるパズルを解く4通りの方法は以下の通りです：

2番目のテストケースにおけるパズルを解く6通りの方法は以下の通りです：

3番目のテストケースにおけるパズルを解く唯一の方法は以下の通りです：

4番目のテストケースでは、パズルを解く方法はありません。

5番目のテストケースでは 'o' セルが存在しないため、パズルを解く唯一の方法は L-トロミノを一切配置しないことです。