在二维宇宙中,一颗恒星可以用二维平面上的点 $$$(x,y)$$$ 来表示。两颗星直接相连当且仅当它们的 $$$x$$$ 或 $$$y$$$ 坐标相同,并且它们之间的线段上没有其他星。将星系定义为由直接或间接(通过其他恒星)连接的恒星组成的连接组件。
对于一组恒星,其值定义为执行以下操作任意(可能为零)次后可获得的最小星系数:在每次操作中,您可以选择一个没有恒星的点$$$(x,y)$$$。如果一个星星在此处创建后可以直接连接到至少 $$$3$$$ 星星,那么您就在这里创建了一个星星。
给你一个 $$$n\times n$$$ 矩阵 $$$a$$$,由 $$$0$$$ 和 $$$1$$$ 组成,描述一组 $$$S$$$ 恒星。当且仅当 $$$a_{x,y}=1$$$ 时,$$$(x,y)$$$ 处有一颗星。计算 $$$S$$$ 的所有非空子集的值的总和(以 $$$10^9 + 7$$$ 为模)。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。
对于每个测试用例,第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 14$$$) — 矩阵 $$$a$$$ 的大小。
然后是 $$$n$$$ 行;第 $$$i$$$ 行包含长度为 $$$n$$$ 的字符串 $$$a_i$$$ — 矩阵 $$$a$$$ 的第 $$$i$$$ 行。
保证所有测试用例的$$$2^n$$$总和不超过$$$2^{14}$$$。
输出
对于每个测试用例,输出 $$$S$$$ 的所有非空子集的值的模 $$$10^9 + 7$$$ 的总和。
示例
输入 #1
8 1 0 2 01 10 3 010 000 101 4 0110 1001 1001 0110 11 11111110111 10000010010 10111010011 10111010011 10111010001 10000010000 11111110101 00000000111 11011010011 10010101100 11101010100 11 11011111110 10010000010 00010111010 10010111010 01010111010 11010000010 01011111110 11000000000 01010000010 01000111100 00000001010 11 11010101001 11001010100 00000000110 11111110010 10000010010 10111010110 10111010111 10111010010 10000010110 11111110100 00000000000 3 111 100 111
输出 #1
0 4 9 355 593092633 438667113 922743932 155
注意
在第一个测试用例中,$$$S$$$ 为空。 $$$S$$$ 没有非空子集。所以答案是$$$0$$$。
在第二个测试用例中,$$$S = \{(1,2),(2,1)\}$$$。 $$$S$$$ 有 $$$3$$$ 非空子集。
- $$$\{(1,2)\}$$$ 和 $$$\{(2,1)\}$$$ — 集合中只有一颗恒星,形成 $$$1$$$ 星系。
- $$$\{(1,2),(2,1)\}$$$ — 集合中的两颗恒星未连接,形成 $$$2$$$ 星系。
所以答案是$$$1+1+2=4$$$。
在第三个测试用例中,$$$S = \{(1,2),(3,1),(3,3)\}$$$。 $$$S$$$ 有 $$$7$$$ 非空子集。
- $$$\{(1,2)\}$$$、$$$\{(3,1)\}$$$ 和 $$$\{(3,3)\}$$$ — 集合中只有一颗恒星,形成 $$$1$$$ 星系。
- $$$\{(1,2),(3,1)\}$$$ 和 $$$\{(1,2),(3,3)\}$$$ — 集合中的两颗恒星没有连接,形成 $$$2$$$ 星系。
- $$$\{(3,1),(3,3)\}$$$ — 集合中的两颗恒星相连,形成 $$$1$$$ 星系。
- $$$\{(1,2),(3,1),(3,3)\}$$$ — 最初,恒星 $$$(1,2)$$$ 不在由 $$$(3,1)$$$ 和 $$$(3,3)$$$ 形成的星系中。您可以进行操作,在 $$$(3,2)$$$ 处创建一颗恒星,连接到这三颗恒星,形成 $$$1$$$ 星系。
所以答案是$$$1+1+1+2+2+1+1=9$$$。