CF1536E.Omkar and Forest

Omkar's most recent follower, Ajit, has entered the Holy Forest. Ajit realizes that Omkar's forest is an $n$ by $m$ grid ($1 \leq n, m \leq 2000$) of some non-negative integers. Since the forest is blessed by Omkar, it satisfies some special conditions:

1. For any two adjacent (sharing a side) cells, the absolute value of the difference of numbers in them is at most $1$.
2. If the number in some cell is strictly larger than $0$, it should be strictly greater than the number in at least one of the cells adjacent to it.

Unfortunately, Ajit is not fully worthy of Omkar's powers yet. He sees each cell as a "0" or a "#". If a cell is labeled as "0", then the number in it must equal $0$. Otherwise, the number in it can be any nonnegative integer.

Determine how many different assignments of elements exist such that these special conditions are satisfied. Two assignments are considered different if there exists at least one cell such that the numbers written in it in these assignments are different. Since the answer may be enormous, find the answer modulo $10^9+7$.

奥姆卡尔最近的追随者阿吉特进入了圣林。阿吉特意识到，奥姆卡尔的森林是一个 $n \times m$ 的网格（$1 \leq n, m \leq 2000$），其中每个格子填有一个非负整数。由于该森林受奥姆卡尔祝福，它满足如下特殊条件：

1. 对任意两个相邻（共享一条边）的格子，其中数字之差的绝对值至多为 $1$；
2. 若某个格子中的数字严格大于 $0$，则它必须严格大于其至少一个相邻格子中的数字。

不幸的是，阿吉特尚未完全配得上奥姆卡尔的力量。他只能将每个格子识别为 "0" 或 "#"：若某格被标记为 "0"，则其中的数字必须等于 $0$；否则，其中的数字可以是任意非负整数。

请确定满足上述特殊条件的数字赋值方案总数。若存在至少一个格子，在两种赋值方案中填入的数字不同，则认为这两种方案不同。由于答案可能极大，请输出答案对 $10^9+7$ 取模的结果。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 100$). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \leq n, m \leq 2000, nm \geq 2$) – the dimensions of the forest.

$n$ lines follow, each consisting of one string of $m$ characters. Each of these characters is either a "0" or a "#".

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$ and the sum of $m$ over all test cases does not exceed $2000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \leq t \leq 100$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 2000$，且 $nm \geq 2$）——表示森林的尺寸。

接下来是 $n$ 行，每行由一个长度为 $m$ 的字符串组成。这些字符串中的每个字符均为 "0" 或 "#"。

保证所有测试用例中 $n$ 的总和不超过 $2000$，且所有测试用例中 $m$ 的总和不超过 $2000$。

For each test case, print one integer: the number of valid configurations modulo $10^9+7$.

对于每个测试用例，输出一个整数：有效配置的数量对 $10^9+7$ 取模的结果。

For the first test case, the two valid assignments are

$0000\\ 0000\\ 0000$

and

$0000\\ 0010\\ 0000$

对于第一个测试用例，两个有效的赋值为

$0000\\ 0000\\ 0000$

和

$0000\\ 0010\\ 0000$