题目描述

每个测试的时间限制：4 秒
内存限制：512 兆字节

在一个二维宇宙中，一颗恒星可以用二维平面上的一个点 $(x, y)$ 来表示。两颗恒星之间直接相连当且仅当它们的 $x$ 坐标或 $y$ 坐标相同，并且它们之间的线段上没有其他恒星。定义一个星系为由恒星直接或间接（通过其他恒星）连接而成的连通分量。

对于一个恒星集合，其价值定义如下：你可以任意次（包括零次）执行以下操作，在操作后能得到的最少星系个数。每次操作：选择一个没有恒星的格点 $(x, y)$，如果在创建该恒星后，它能够与至少 $3$ 颗恒星直接相连，那么就在此处创建一颗恒星。

给定一个 $n \times n$ 的 $0/1$ 矩阵 $a$，它描述了恒星集合 $S$。当且仅当 $a_{x,y}=1$ 时，在 $(x,y)$ 处有一颗恒星。请计算 $S$ 的所有非空子集的价值的和，并对 $10^9+7$ 取模。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 100$）——测试用例的数量。
对于每个测试用例，第一行包含一个整数 $n$（$1 \le n \le 14$）——矩阵 $a$ 的大小。
接下来 $n$ 行，第 $i$ 行包含一个长度为 $n$ 的字符串 $a_i$ ——矩阵 $a$ 的第 $i$ 行。
保证所有测试用例的 $2^n$ 之和不超过 $2^{14}$。

输出格式

对于每个测试用例，输出所有非空子集的价值之和，对 $10^9+7$ 取模。

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

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+2+2+1+1=9$。