У Байтазара есть $n$ лампочек, пронумерованных числами от 1 до $n$, и $m$ переключателей. Каждая лампочка изначально либо включена, либо выключена. Каждый переключатель воздействует на определенную пару лампочек. Его использование меняет состояние обеих лампочек на противоположное, но только при условии, что обе они находились в одинаковом состоянии — обе включены или обе выключены. В противном случае нажатие переключателя не дает никакого эффекта.

Байтазар хочет узнать, сколько различных конфигураций включенных и выключенных лампочек он может получить, используя переключатели любое количество раз в любом порядке, потенциально используя некоторые переключатели многократно. Две конфигурации считаются различными, если хотя бы одна лампочка включена в одной конфигурации и выключена в другой. Поскольку результат может быть очень большим, достаточно вывести его остаток от деления на $10^9 + 7$.

Входные данные

В первой строке входных данных находятся два целых числа $n$ и $m$ ($1 \le n \le 200\,000$; $0 \le m \le 400\,000$), обозначающие количество лампочек и количество переключателей соответственно.

Во второй строке находятся $n$ чисел $c_i$ ($c_i \in \{0, 1\}$), разделенных пробелами. Если $c_i = 1$, то $i$-я лампочка изначально включена. В противном случае (если $c_i = 0$), $i$-я лампочка изначально выключена.

В следующих $m$ строках содержатся описания переключателей; $i$-я из этих строк содержит два целых числа $a_i$ и $b_i$ ($1 \le a_i, b_i \le n$; $a_i \neq b_i$) — номера лампочек, на которые воздействует $i$-й переключатель.

Можно считать, что переключатели воздействуют на различные неупорядоченные пары лампочек. Формально, для любой пары различных индексов $i, j$ от 1 до $m$ включительно выполняется $(a_i, b_i) \neq (a_j, b_j)$ и $(a_i, b_i) \neq (b_j, a_j)$.

Выходные данные

В первой и единственной строке вывода должно содержаться количество достижимых конфигураций включенных и выключенных лампочек по модулю $10^9 + 7$.

Примеры

Пример 1

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

Выходные данные 1

4

Примечание

Достижимые конечные состояния лампочек: 10110, 00010, 00111 и 10011.