E. Омкар и лес
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Последний присоединившийся последователь Омкара, Ajit, вошел в Священный лес. Ajit понимает, что лес Омкара — это таблица размером $$$n$$$ на $$$m$$$ ($$$1 \leq n, m \leq 2000$$$), состоящая из целых неотрицательных чисел. Поскольку лес благословлен Омкаром, он удовлетворяет некоторым особым условиям:

  1. Для любых двух соседних по стороне клеток абсолютное значение разности чисел в них не превышает $$$1$$$.
  2. Если число в какой-то клетке строго больше $$$0$$$, то оно должно быть строго больше, чем значение числа в по крайней мере одной клетке, примыкающей к ней по стороне.

К сожалению, Ajit еще не полностью достоин способностей Омкара. Он видит каждую клетку как "0" или "#". Если клетка обозначена как "0", то число в ней должно быть равно $$$0$$$. Иначе число в ней может быть любым неотрицательным целым числом.

Определите, сколько существует различных конфигураций элементов, при которых выполняются эти особые условия. Две конфигурации считаются различными, если существует хотя бы одна клетка такая, что числа, записанные в ней в этих конфигурациях, различны. Поскольку ответ может быть огромным, найдите ответ по модулю $$$10^9+7$$$.

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

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \leq t \leq 100$$$). Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 2000, nm \geq 2$$$) — размеры леса.

Далее следуют $$$n$$$ строк, каждая из которых состоит из одной строки из $$$m$$$ символов. Каждый из этих символов является либо "0", либо "#".

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2000$$$, а также сумма $$$m$$$ по всем наборам входных данных не превышает $$$2000$$$.

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

Для каждого набора входных данных выведите одно целое число: количество допустимых конфигураций по модулю $$$10^9+7$$$.

Пример
Входные данные
4
3 4
0000
00#0
0000
2 1
#
#
1 2
##
6 29
#############################
#000##0###0##0#0####0####000#
#0#0##00#00##00####0#0###0#0#
#0#0##0#0#0##00###00000##00##
#000##0###0##0#0##0###0##0#0#
#############################
Выходные данные
2
3
3
319908071
Примечание

Для первого набора входных данных есть две допустимых конфигурации:

$$$0000\\ 0000\\ 0000$$$

и

$$$0000\\ 0010\\ 0000$$$