Gxor

There is a fixed integer n. All graphs in this problem are undirected unweighted graphs on n vertices. The vertices in each graph are numbered 0 through n-1. Additionally, all graphs are simple, i.e., they do not contain self-loops and multiple edges between the same two vertices.

Given a sequence X of such graphs, the xor of that sequence is again a graph on our n vertices. We will denote this graph XOR(X). For each u and v, vertices u and v are connected by an edge in XOR(X) if and only if the number of graphs in X that contain the edge uv is odd. (In other words, the xor of two graphs is a graph that contains the edge uv if and only if exactly one of those two graphs contains the edge uv. We then extend this definition to a xor of arbitrarily many graphs in exactly the same way that is used to extend the bitwise xor to arbitrarily many integers.)

Given a graph, we can convert it into a string using the following pseudocode:

string(G):
    for u = 0 .. n-1:
        for v = u+1 .. n-1:
            if G contains the edge uv: print 1
            else: print 0

You are given a String[] S that describes a sequence S of n-vertex graphs. Each element of S is the string representation of one of those graphs.

We want to erase some (possibly none, possibly all) graphs from S. Our goal is to produce a sequence T such that XOR(T) is a connected graph. Return the number of ways in which we can do that. (Two ways are considered distinct if the sets of indices of erased graphs differ.)

Note that all n vertices of the graph XOR(T) have to be in the same connected component - there must not be any isolated vertices.