Bajtazar has $n$ light bulbs numbered with consecutive integers from $1$ to $n$, and $m$ switches. Each light bulb is initially either on or off. Each switch affects a specific pair of light bulbs. Using a switch toggles the state of both bulbs, but only if they are in the same state—both on or both off. Otherwise, pressing the switch has no effect.

Bajtazar wonders how many different configurations of on and off bulbs he can reach by using the switches any number of times in any order, potentially using some switches multiple times. Two configurations are considered different if at least one bulb is on in one configuration and off in the other. Since the result can be large, it is sufficient to provide the result modulo $10^9 + 7$.

Input

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

The second line of input contains $n$ integers $c_i$ ($c_i \in \{0, 1\}$) separated by single spaces. If $c_i = 1$, the $i$-th bulb is initially on. Otherwise (if $c_i = 0$), the $i$-th bulb is initially off.

The next $m$ lines contain descriptions of the switches; the $i$-th of these lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$) — the numbers of the bulbs affected by the $i$-th switch.

You may assume that the switches affect distinct unordered pairs of bulbs. Formally, for every pair of distinct indices $i, j$ between $1$ and $m$ inclusive, $(a_i, b_i) \neq (a_j, b_j)$ and $(a_i, b_i) \neq (b_j, a_j)$.

Output

The first and only line of output should contain the number of reachable configurations of on and off bulbs modulo $10^9 + 7$.

Examples

Input 1

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

Output 1

4

Note

The reachable final states of the bulbs are 10110, 00010, 00111, and 10011.