Bajtazar は、$1$ から $n$ までの番号が付けられた $n$ 個の電球と、$m$ 個のスイッチを持っています。各電球は最初、点灯しているか消灯しているかのいずれかです。各スイッチはある特定の電球のペアに影響を与えます。スイッチを使用すると、そのペアの両方の電球の状態が反転します。ただし、これは両方の電球が同じ状態（両方とも点灯、または両方とも消灯）である場合にのみ発生します。電球の状態が異なる場合、スイッチを押しても何も起こりません。

Bajtazar は、スイッチを何度でも、どのような順序でも使用できるとき、到達可能な電球の点灯・消灯パターンの総数がいくつあるかを知りたいと考えています。ある電球が一方の構成では点灯しており、もう一方の構成では消灯している場合、それらの構成は異なるとみなします。結果は非常に大きくなる可能性があるため、$10^9 + 7$ で割った余りを出力してください。

入力

入力の最初の行には、電球の数 $n$ とスイッチの数 $m$ を表す2つの整数 ($1 \le n \le 200\,000$; $0 \le m \le 400\,000$) が含まれます。

2行目には、$n$ 個の整数 $c_i$ ($c_i \in \{0, 1\}$) が空白区切りで含まれます。$c_i = 1$ の場合、$i$ 番目の電球は最初点灯しています。それ以外の場合 ($c_i = 0$)、$i$ 番目の電球は最初消灯しています。

続く $m$ 行にはスイッチの説明が含まれます。$i$ 番目の行には、$i$ 番目のスイッチが影響を与える電球の番号を表す2つの整数 $a_i$ と $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$) が含まれます。

スイッチはそれぞれ異なる電球のペアに影響を与えるものと仮定して構いません。より厳密には、すべての異なるインデックスのペア $i, j$ ($1 \le i, j \le m$) に対して、$(a_i, b_i) \neq (a_j, b_j)$ かつ $(a_i, b_i) \neq (b_j, a_j)$ が成り立ちます。

出力

出力の最初の1行に、到達可能な電球の点灯・消灯パターンの総数を $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 です。