Background

PA 2024 5C2

Problem Description

This problem is translated from PA 2024 Round 5 Żarówki. Thanks to Macaronlin for providing the translation.

There are $n$ light bulbs. Each bulb has two states: on and off, and the initial state is given. There are $m$ switches. Each switch controls two bulbs. Pressing a switch will flip these two bulbs to the opposite of their current states, but it works only when the two bulbs are in the same state; otherwise, it has no effect.

You may choose the order of using switches and the number of times to use them freely. Ask how many different configurations can be achieved using these switches. If a bulb is on in one configuration and off in another, then the two configurations are considered different.

Input Format

The first line contains two integers $n$ and $m\ (1\le n\le 200\,000,0\le m\le 400\,000)$, representing the number of bulbs and switches.

The second line contains $n$ integers $c_i\ (c_i\in \{0,1\})$. If $c_i=1$, then bulb $i$ is initially on; if $c_i=0$, then bulb $i$ is initially off.

The next $m$ lines each contain two integers $a_i,b_i\ (1\le a_i,b_i\le n,a_i\neq b_i)$, describing a switch.

It is guaranteed that each switch affects a different unordered pair of bulbs. Formally, $\forall i,j \in \{1,2,\ldots,m\},i\neq j$, we have $(a_i,b_i)\neq (a_j,b_j)$ and $(a_i,b_i)\neq (b_j,a_j)$.

Output Format

Output one integer on a single line, representing how many configurations can be achieved using these switches. Output the answer modulo $10^9+7$.

5 4
1 0 1 1 0
1 3
5 3
4 2
1 5

4

Hint

All achievable configurations are: 10110, 00010, 00111, and 10011.

Translated by ChatGPT 5