You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

限制

• 1000 ms
• 524288 KB

文件

link

小王来到了一片森林，森林中有一些树和连接两棵树的无向道路。

小王对这片森林做了一些考察，有了两个奇怪的发现：

$1$）森林中的树总共分为两种，不妨记为 $0$ 型树和 $1$ 型树。 ​
$2$）这些道路的长度都是 $2$ 的整数次幂且互不相同，第 $i$ 条道路的长度为 $2^i$。

小王又发现了这片森林的一个神奇之处，任何两棵类型不同的树之间都可以构成一组链接，这一对链接的能量值为两棵树之间的最短路。

好奇的小王想知道这片森林所有链接的能量值之和，请你来帮帮他。

输入格式

输入第一行包含两个整数 $n,m$，表示森林中树的数量和无向道路的数量。

接下来一行包含 $n$ 个整数 $a_1,a_2,...,a_n(a_i=0\ or\ 1)$，表示每一棵树的类型。

接下来 $m$ 行，第 $i$ 行表示第 $i$ 条无向道路，包含两个整数 $u_i,v_i(1\leq u_i,v_i \leq n)$ 表示第 $i$ 条无向道路连接的树的编号，并且它的长度为 $2^i$。

输出格式

输出一个整数，所有链接能量值之和对 $10^9+7$ 取模的结果。

样例输入 1

3 2
0 1 0
3 1
1 2

样例输出 1

10

数据范围

对于 $20\%$ 的数据，$n\leq 10$

对于 $40\%$的数据，$n\leq 20$

对于 $100\%$ 的数据，$n\leq 100000, 1\leq m\leq 200000$