Omkar and Forest

题意翻译

给定 $n,m$ 和一个 $n$ 行 $m$ 列、仅包含字符 `0 #` 的网格。 你需要向网格上每个位置都分配一个非负整数，我们认为这个网格是“好的”仅当： - 对于任意两个相邻的格子，这两个格子其中的数的差的绝对值不超过 $1$。 - 如果一个格子里的数为正整数，那么与这个格子相邻的四个格子中至少有一个格子里的数比这个格子的数小。 如果这个网格中为字符 `0` 的位置上必须为 $0$，否则可以是任意非负整数，求有多少种互不相同的方案使得这个网格是“好的”。答案对 $10^9+7$ 取模。 $T$ 组数据。 $1\leq n,m,\sum n,\sum m\leq2\times10^3;n\times m\geq2;$ 网格中仅包含字符 `0 #`。

题目描述

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 $ .

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

输入样例 #1

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#
#############################

输出样例 #1

2
3
3
319908071

说明

For the first test case, the two valid assignments are $ 0000\\ 0000\\ 0000 $ and $ 0000\\ 0010\\ 0000 $

题意翻译

给定 $n,m$ 和一个 $n$ 行 $m$ 列、仅包含字符 `0 #` 的网格。 你需要向网格上每个位置都分配一个非负整数，我们认为这个网格是“好的”仅当： - 对于任意两个相邻的格子，这两个格子其中的数的差的绝对值不超过 $1$。 - 如果一个格子里的数为正整数，那么与这个格子相邻的四个格子中至少有一个格子里的数比这个格子的数小。 如果这个网格中为字符 `0` 的位置上必须为 $0$，否则可以是任意非负整数，求有多少种互不相同的方案使得这个网格是“好的”。答案对 $10^9+7$ 取模。 $T$ 组数据。 $1\leq n,m,\sum n,\sum m\leq2\times10^3;n\times m\geq2;$ 网格中仅包含字符 `0 #`。