Graph Color Flipping Game

Two researchers, C and G, are studying a gaming problem based on graphs and flipping operations. You are given an undirected graph with $n$ vertices and $m$ edges. Each vertex is initially colored either black or white (denoted by 'B' and 'W', respectively). For every edge, you can independently decide either to flip the colors of both endpoints (black to white and white to black) or to do nothing. The goal is to make all vertices white.

Formally, if we let each vertex have an initial value $a_i$ (with white as 0 and black as 1) and we choose a binary variable $x_e$ for each edge (with $1$ meaning the edge is chosen to flip and $0$ meaning no change), then for every vertex $i$, the condition to have final color white is:

The number of valid selections is the number of solutions of this system modulo $10^9+7$. It can be shown that for each connected component, if the component is bipartite then a necessary and sufficient condition for existence of a solution is that the sum of $a_i$ in the component is even, and the number of free variables is edges − (vertices − 1); if the component is non‐bipartite then the system is always solvable and the number of free variables is edges − vertices (since the incidence matrix over $\mathbb{F}_2$ has full rank in that case). Consequently, if we let $B$ be the number of bipartite connected components in the graph then the overall number of solutions is

provided that every bipartite component satisfies the parity condition; otherwise the answer is 0.

Moreover, for each vertex $i$, you are asked to compute the number of valid ways if vertex $i$ (and all edges incident to it) is removed from the graph.

inputFormat

The input consists of:

• First line: two integers $n$ and $m$, which denote the number of vertices and edges respectively.
• Second line: a string of length $n$ composed of the characters 'B' and 'W', representing the initial colors of the vertices (1-indexed). 'B' corresponds to black (value 1) and 'W' to white (value 0).
• Next $m$ lines: each contains two integers $u$ and $v$ (1-indexed) representing an undirected edge between vertices $u$ and $v$.

outputFormat

Output $n+1$ lines. The first line is the number of valid selections for the original graph modulo $10^9+7$. Each of the following $n$ lines (line $i+1$) should contain the answer for the graph obtained after removing vertex $i$ and all edges incident to it (again, modulo $10^9+7$).

sample

3 3
BWB
1 2
2 3
3 1

1
0
1
0