Busy Beaver нашел странную головоломку. Головоломка состоит из коробки, разделенной на сетку $N \times M$ квадратов. Каждая ячейка сетки либо занята (обозначена «#»), либо пуста (обозначена «.»), либо пуста, но помечена «o».

Головоломка поставляется с набором L-тримино, по одному для каждой ячейки «o» на сетке. L-тримино состоит из трех квадратных блоков в форме буквы L, как показано на рисунке. Центром L-тримино является квадрат, который граничит с двумя другими квадратами (на рисунке помечен буквой o).

Busy Beaver понимает, что для решения головоломки ему нужно упаковать все L-тримино в коробку так, чтобы L-тримино были выровнены по сетке, центр каждого L-тримино находился в пустой ячейке, помеченной «o», и никакие два 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» находится на манхэттенском расстоянии не менее 3 от каждой другой ячейки «o». То есть, если $(r_1, c_1)$ и $(r_2, c_2)$ — две разные ячейки «o», то $|r_1 - r_2| + |c_1 - c_2| \ge 3$.
• (30 баллов) Каждая ячейка «o» вертикально соседствует по крайней мере с одной другой ячейкой «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..###
2 3
#.o
.o.
2 2
..
..

Выходные данные 1

4
6
1
0
1

Примечание

Заметьте, что первый тестовый случай удовлетворяет ограничениям первой подзадачи, а второй тестовый случай удовлетворяет ограничениям второй подзадачи.

В первом тестовом случае 4 способа решить головоломку показаны на рисунках.

Во втором тестовом случае 6 способов решить головоломку показаны на рисунках.

В третьем тестовом случае единственный способ решить головоломку показан на рисунке.

В четвертом тестовом случае нет способов решить головоломку.

В пятом тестовом случае нет ячеек «o», поэтому единственный способ решить головоломку — не размещать никаких L-тримино.