CF2062H Galaxy Generator

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 $ .

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} $ .

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

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 $ .