CF2062H.Galaxy Generator

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

对于一个恒星集合，其价值定义为：经过任意次（可能为零次）以下操作后，能够得到的最小星系数量。每次操作中，你可以选择一个没有恒星的位置 $(x, y)$。如果在此处创建恒星后，该恒星能够直接连接到至少 $3$ 颗恒星，则你可以在此处创建一颗新恒星。

给定一个由 $0$ 和 $1$ 组成的 $n \times n$ 矩阵 $a$，描述一个恒星集合 $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}$。

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

第一个测试用例中，$S$ 为空集。由于没有非空子集，答案为 $0$。

第二个测试用例中，$S = \{(1,2), (2,1)\}$，共有 $3$ 个非空子集：

• $\{(1,2)\}$ 和 $\{(2,1)\}$：仅有一个恒星，形成 $1$ 个星系。
• $\{(1,2), (2,1)\}$：两颗恒星不相连，形成 $2$ 个星系。
  因此答案为 $1 + 1 + 2 = 4$。

第三个测试用例中，$S = \{(1,2), (3,1), (3,3)\}$，共有 $7$ 个非空子集：

• 单恒星子集：各形成 $1$ 个星系。
• $\{(1,2), (3,1)\}$ 和 $\{(1,2), (3,3)\}$：不相连，各形成 $2$ 个星系。
• $\{(3,1), (3,3)\}$：直接相连，形成 $1$ 个星系。
• 全集 $\{(1,2), (3,1), (3,3)\}$：初始时 $(1,2)$ 与其他恒星不连通。可通过在 $(3,2)$ 处创建恒星（连接到三个恒星）合并为 $1$ 个星系。
  因此答案为 $1 + 1 + 1 + 2 + 2 + 1 + 1 = 9$。

翻译由 DeepSeek R1 完成