Bajtazar 擁有 $n$ 個編號從 $1$ 到 $n$ 的燈泡以及 $m$ 個開關。每個燈泡初始時可能為開啟或關閉狀態。每個開關會影響一對燈泡。使用開關會將這兩個燈泡的狀態同時反轉，但前提是這兩個燈泡目前的狀態必須相同（皆為開啟或皆為關閉）。如果狀態不同，按下開關將不會有任何效果。

Bajtazar 想知道，透過任意次數、任意順序地使用這些開關，他總共能達到多少種不同的燈泡開啟與關閉配置。若兩個配置中存在至少一個燈泡的狀態不同，則視為不同的配置。由於結果可能很大，請輸出其對 $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 \le i, j \le 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

說明 1

可達到的最終燈泡狀態為 10110、00010、00111 與 10011。