CF1536E Omkar and Forest

Omkar 的最新追随者 Ajit 进入了神圣森林。Ajit 发现 Omkar 的森林是一个 $n \times m$ 的网格（$1 \leq n, m \leq 2000$），每个格子里有一些非负整数。由于森林受到了 Omkar 的祝福，它满足以下特殊条件： 1. 对于任意两个相邻（共享一条边）的格子，它们之间的数的差的绝对值至多为 $1$。 2. 如果某个格子里的数严格大于 $0$，那么它必须严格大于至少一个相邻格子里的数。 不幸的是，Ajit 还没有完全获得 Omkar 的力量。他只能看到每个格子是 “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$ 取模。

对于第一个测试用例，两个合法的赋值方案为 $0000\\ 0000\\ 0000$ 和 $0000\\ 0010\\ 0000$ 由 ChatGPT 4.1 翻译