奥姆卡的最新追随者阿吉特已进入圣林。 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$$$