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\}$。

输出格式

输出一行，包含可达到的灯泡配置总数对 $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。