Bajtazar posee $n$ bombillas numeradas con números consecutivos del 1 al $n$ y $m$ interruptores. Cada bombilla está inicialmente encendida o apagada. Cada interruptor afecta a un par determinado de bombillas. Al usarlo, el estado de ambas bombillas cambia al opuesto, pero solo bajo la condición de que ambas estuvieran en el mismo estado: ambas encendidas o ambas apagadas. De lo contrario, presionar el interruptor no tendrá ningún efecto.

Bajtazar se pregunta cuántas configuraciones diferentes de bombillas encendidas y apagadas puede alcanzar utilizando los interruptores tantas veces como desee y en cualquier orden, pudiendo utilizar algunos interruptores varias veces. Dos configuraciones se consideran diferentes si alguna bombilla está encendida en una configuración y apagada en la otra. Dado que el resultado puede ser muy grande, basta con que proporciones su resto al dividirlo por $10^9 + 7$.

Entrada

La primera línea de la entrada contiene dos números enteros $n$ y $m$ ($1 \le n \le 200\,000$; $0 \le m \le 400\,000$), que representan el número de bombillas y el número de interruptores, respectivamente.

La segunda línea de la entrada contiene $n$ números $c_i$ ($c_i \in \{0, 1\}$) separados por espacios. Si $c_i = 1$, la $i$-ésima bombilla está inicialmente encendida. De lo contrario (si $c_i = 0$), la $i$-ésima bombilla está inicialmente apagada.

Las siguientes $m$ líneas contienen las descripciones de los interruptores; la $i$-ésima de estas líneas contiene dos números enteros $a_i$ y $b_i$ ($1 \le a_i, b_i \le n$; $a_i \neq b_i$), los números de las bombillas sobre las que influye el $i$-ésimo interruptor.

Puedes asumir que los interruptores afectan a pares de bombillas no ordenados distintos. Formalmente, para cada par de índices distintos $i, j$ entre $1$ y $m$ inclusive, se cumple que $(a_i, b_i) \neq (a_j, b_j)$ y $(a_i, b_i) \neq (b_j, a_j)$.

Salida

La primera y única línea de salida debe contener el resto de la división por $10^9 + 7$ del número de configuraciones alcanzables de bombillas encendidas y apagadas.

Ejemplos

Entrada 1

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

Salida 1

4

Nota

Los estados finales alcanzables de las bombillas son 10110, 00010, 00111 y 10011.