← 返回题目列表

Codeforces · 1536/E

E. 奥姆卡和森林

中文机器翻译题面 查看原题

奥姆卡的最新追随者阿吉特已进入圣林。 Ajit 认识到 Omkar 的森林是 $$$n$$$ 由 $$$m$$$ 网格 ($$$1 \leq n, m \leq 2000$$$) 组成的一些非负整数。由于森林受到奥姆卡的祝福,它满足一些特殊的条件:

1. 对于任意两个相邻(共享一条边)的单元格,它们中的数字之差的绝对值最多为$$$1$$$。
2. 如果某个单元格中的数字严格大于 $$$0$$$,则该数字应严格大于与其相邻的至少一个单元格中的数字。

不幸的是,阿吉特还不能完全配得上奥姆卡的力量。他将每个单元格视为“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$$$ 为模。

示例

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

注意

对于第一个测试用例,两个有效分配是

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

和

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