Busy Beaver znalazł dziwną łamigłówkę. Łamigłówka składa się z pudełka podzielonego na siatkę kwadratów o wymiarach $N \times M$. Każda komórka siatki jest albo zajęta (oznaczona jako '#'), pusta (oznaczona jako '.'), albo pusta, ale oznaczona jako 'o'.

Łamigłówka zawiera zestaw elementów typu L-tromino, po jednym dla każdej komórki 'o' w siatce. L-tromino składa się z trzech kwadratowych bloków w kształcie litery L, jak pokazano na rysunku poniżej. Środek L-tromino to kwadrat, który sąsiaduje z oboma pozostałymi kwadratami (oznaczony jako 'o' na rysunku).

Rysunek 1: Kształt L-tromino. Środek oznaczony jako 'o'.

Busy Beaver zdaje sobie sprawę, że aby rozwiązać łamigłówkę, musi umieścić wszystkie elementy L-tromino w pudełku w taki sposób, aby elementy L-tromino były wyrównane do siatki, środek każdego L-tromino znajdował się w pustej komórce oznaczonej jako 'o', a żadne dwa elementy L-tromino nie nachodziły na siebie ani na zajętą komórkę. Wszystkie elementy L-tromino można dowolnie obracać.

Czy możesz pomóc Busy Beaverowi policzyć liczbę sposobów rozwiązania łamigłówki? Ponieważ odpowiedź może być duża, wyprowadź ją modulo $10^9 + 7$.

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwsza linia zawiera liczbę przypadków testowych $T$ ($1 \le T \le 500$). Następnie następuje opis przypadków testowych.

Pierwsza linia każdego przypadku testowego zawiera dwie liczby całkowite $N$ i $M$ ($2 \le N, M \le 1000$), wymiary siatki.

Kolejne $N$ linii zawiera po $M$ znaków, opisujących wiersz siatki. Każdy znak to '#', '.' lub 'o'.

Gwarantuje się, że suma $N$ we wszystkich przypadkach testowych nie przekracza 1000. Gwarantuje się, że suma $M$ we wszystkich przypadkach testowych nie przekracza 1000.

Wyjście

Dla każdego przypadku testowego wyprowadź pojedynczą liczbę całkowitą: liczbę sposobów rozwiązania łamigłówki modulo $10^9 + 7$.

Podzadania

Niech $(r, c)$ oznacza komórkę w wierszu $r$ i kolumnie $c$ ($1 \le r \le N, 1 \le c \le M$).

• (10 punktów) Każda komórka 'o' znajduje się w odległości Manhattan co najmniej 3 od każdej innej komórki 'o'. Oznacza to, że jeśli $(r_1, c_1)$ i $(r_2, c_2)$ są dwiema różnymi komórkami 'o', to $|r_1 - r_2| + |c_1 - c_2| \ge 3$.
• (30 punktów) Każda komórka 'o' sąsiaduje pionowo z co najmniej jedną inną komórką 'o' lub '#'. Oznacza to, że dla każdej komórki 'o' w $(r, c)$, albo $(r - 1, c)$, albo $(r + 1, c)$ jest komórką '#' lub inną komórką 'o'.
• (60 punktów) Brak dodatkowych ograniczeń.

Przykład

Wejście 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..###
2 3
#.o
.o.
2 2
..
..

Wyjście 1

4
6
1
0
1

Uwagi

Zauważ, że pierwszy przypadek testowy spełnia ograniczenia dla pierwszego podzadania, a drugi przypadek testowy spełnia ograniczenia dla drugiego podzadania.

W pierwszym przypadku testowym 4 sposoby rozwiązania łamigłówki wyglądają następująco:

W drugim przypadku testowym 6 sposobów rozwiązania łamigłówki wygląda następująco:

W trzecim przypadku testowym jedyny sposób rozwiązania łamigłówki wygląda następująco:

W czwartym przypadku testowym nie ma sposobów rozwiązania łamigłówki.

W piątym przypadku testowym nie ma komórek 'o', więc jedynym sposobem rozwiązania łamigłówki jest nieumieszczanie żadnych elementów L-tromino.