Background

This problem comes from the original BZOJ. We acknowledge that the copyright of the statement and the original testdata belongs to the original BZOJ or the problem setter(s) who authorized BZOJ to use the problem. If you are the copyright owner and believe that we have infringed your rights, please contact us.

Problem Description

Define the XOR of two graphs $G_1$ and $G_2$ with the same number of vertices as a new graph $G$. If the total number of occurrences of $(u, v)$ in $G_1$ and $G_2$ is $1$, then the edge $(u, v)$ is in $G$; otherwise, this edge is not in $G$.

Now you are given $s$ graphs $G_{1\sim s}$ with the same number of vertices, $S=\{G_1,G_2,\dots,G_s\}$. How many subsets of $S$ have an XOR that is a connected graph?

Input Format

The first line contains an integer $s$, representing the number of graphs.

Each of the following lines contains a binary string. The binary string on line $i$ is $g_i$, where $g_i$ is obtained from the original graph by the following pseudocode. The vertices are numbered starting from $1$, and let the number of vertices be $n$.

Algorithm 1 Print a graph G = (V, E)

for i = 1 to n do
    for j = i + 1 to n do
        if G contains edge (i, j) then
            print 1
        else
            print 0
        end if
    end for
end for

Output Format

Output one line containing an integer, representing the number of valid ways.

3 
1 
1 
0

4

Hint

For $100\%$ of the data, $2\leq n\leq 10$ and $1\leq s\leq 60$.

Translated by ChatGPT 5