Galaxy Generator
Contest: Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: bitmasks, combinatorics, dp

In a two-dimensional universe, a star can be represented by a point $$$(x,y)$$$ on a two-dimensional plane. Two stars are directly connected if and only if their $$$x$$$ or $$$y$$$ coordinates are the same, and there are no other stars on the line segment between them. Define a galaxy as a connected component composed of stars connected directly or indirectly (through other stars).

For a set of stars, its value is defined as the minimum number of galaxies that can be obtained after performing the following operation for any (possibly, zero) times: in each operation, you can select a point $$$(x,y)$$$ without stars. If a star can be directly connected to at least $$$3$$$ stars after creating it here, then you create a star here.

You are given a $$$n\times n$$$ matrix $$$a$$$ consisting of $$$0$$$ and $$$1$$$ describing a set $$$S$$$ of stars. There is a star at $$$(x,y)$$$ if and only if $$$a_{x,y}=1$$$. Calculate the sum, modulo $$$10^9 + 7$$$, of the values of all non-empty subsets of $$$S$$$.

Input format:
The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

For each test case, the first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 14$$$) — the size of matrix $$$a$$$.

Then $$$n$$$ lines follow; the $$$i$$$-th line contains a string $$$a_i$$$ of length $$$n$$$ — the $$$i$$$-th row of matrix $$$a$$$.

It is guaranteed that the sum of $$$2^n$$$ over all test cases does not exceed $$$2^{14}$$$.

Output format:
For each test case, output the sum, modulo $$$10^9 + 7$$$, of the values of all non-empty subsets of $$$S$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first test case, $$$S$$$ is empty. $$$S$$$ has no non-empty subsets. So the answer is $$$0$$$.

In the second test case, $$$S = \{(1,2),(2,1)\}$$$. $$$S$$$ has $$$3$$$ non-empty subsets.

- $$$\{(1,2)\}$$$ and $$$\{(2,1)\}$$$ — there is only one star in the set, forming $$$1$$$ galaxy.
- $$$\{(1,2),(2,1)\}$$$ — two stars in the set are not connected, forming $$$2$$$ galaxies.

So the answer is $$$1+1+2=4$$$.

In the third test case, $$$S = \{(1,2),(3,1),(3,3)\}$$$. $$$S$$$ has $$$7$$$ non-empty subsets.

- $$$\{(1,2)\}$$$, $$$\{(3,1)\}$$$, and $$$\{(3,3)\}$$$ — there is only one star in the set, forming $$$1$$$ galaxy.
- $$$\{(1,2),(3,1)\}$$$ and $$$\{(1,2),(3,3)\}$$$ — two stars in the set are not connected, forming $$$2$$$ galaxies.
- $$$\{(3,1),(3,3)\}$$$ — two stars in the set are connected, forming $$$1$$$ galaxy.
- $$$\{(1,2),(3,1),(3,3)\}$$$ — initially, star $$$(1,2)$$$ is not in the galaxy formed by $$$(3,1)$$$ and $$$(3,3)$$$. You can make an operation creating a star at $$$(3,2)$$$ connecting to these three stars, forming $$$1$$$ galaxy.

So the answer is $$$1+1+1+2+2+1+1=9$$$.

Example input:
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

Example output:
0
4
9
355
593092633
438667113
922743932
155

Editorial:
We will refer to the smallest rectangle containing a galaxy whose edges are parallel to the coordinate axis as the boundary rectangle of a galaxy. For two galaxies, if the projections of their boundary rectangles intersect on the x or y axis, we can merge these two galaxies in one operation.
Proof: Let's assume that the projections of two rectangles on the x-axis intersect. If their projections on the x-axis are $$$(l_1, r_1)$$$ and $$$(l_2, r_2)$$$, let $$$l_1<l_2$$$, then $$$l_2<r_1$$$. Since stars in a galaxy must be connected, there must be two stars in the first galaxy with x-coordinates on either side of $$$x=l_2$$$ that are directly connected. Creating a star at the intersection of the line segment between these two stars and $$$x=l_2$$$ can connect two galaxies. The situation is the same for the y-axis.
Consider continuously merging two galaxies that meet the above conditions until the projections of the boundary rectangles of all galaxies on the x-axis and y-axis are non intersecting. The set of boundary rectangles obtained in this way must be uniquely determined because such rectangles cannot be merged or split into smaller rectangles that cannot be merged.
Next, we need to calculate the number of subsets of stars for each two-dimensional interval, so that all stars in this subset can obtain a unique galaxy through the above process, and the boundary rectangle of this galaxy is the two-dimensional interval. The answer can be calculated using the inclusion exclusion method, because if these stars cannot form such a galaxy, then they must have formed several smaller rectangles with projection intervals that do not intersect on the x-axis and y-axis.
We can continuously add these smaller rectangles from left to right in the x-axis direction. At the same time, maintain the bitmask of the union of these rectangular projections in the y-axis direction to ensure that these rectangles do not intersect. To reduce time complexity, calculations can be performed simultaneously for all two-dimensional intervals. We can perform interval dp in the x-axis direction and directly calculate the entire set in the y-axis direction and use high-dimensional prefix sum to obtain answers for each interval.
The time complexity of this dp method appears to be $$$O (2^n \cdot n^5)$$$, because we need to enumerate the left boundary where the x-axis transition begins, the bitmask in the y-axis direction, and the four boundaries of the concatenated small rectangle when concatenating them. However, since the interval in the y-axis direction must not intersect with the bitmask, in reality, the enumeration here only needs to be calculated $$$\sum_{i=1}^n (n-i+1) \cdot 2^{n-i} = O(2^n \cdot n)$$$ times. So the final time complexity is $$$O (2^n \cdot n^4)$$$.