You are given a String[] **graph**, containing *N* elements and representing an undirected graph on *N* vertices. The *j*-th character in the *i*-th element of **graph** (which is the same as the *i*-th character in the *j*-th element of **graph**) is 'Y' if the *i*-th and *j*-th vertices of the graph are connected by an edge, and is 'N' otherwise.
You should label each vertex of the graph with an integer between 1 and **M**, inclusive, and then label each edge with the sum of its end vertices' labels. The labeling of vertices is called *magic* if each edge is labeled with the same integer. Two labelings of vertices are considered distinct if there's at least one vertex which has different labels in these labelings. Calculate the total count of distinct magic labelings of the given graph. Return this number modulo 1,000,003. |