土豆王国即将遭到邪恶的 Heltion 王国的袭击！作为国防部长，小 Sub 必须非常仔细地安排防御系统。
土豆王国一共有 $n$ 座城堡，小 Sub 计划在其中一些城堡上装备大炮。然而，如果两座城堡距离太近，它们就不能同时装备大炮，因为它们可能会互相误伤。
第 $i$ 座城堡的防御值为 $w_i$。设 $C$ 为所有装备了大炮的城堡的下标集合，我们定义总防御值为： $$\prod_{k \in C} w_k$$
为了完整性，如果 $C = \emptyset$，总防御值定义为 $1$。
给这些城堡装备大炮有许多种可能的方案，小 Sub 必须选择一个合适的方案。为了更准确地评估局势，他想知道所有可行方案的总防御值的方差 $S^2$（注意，不给任何城堡装备大炮也是一种可行方案）。
如果一个城堡在方案 $A$ 中装备了大炮，但在方案 $B$ 中没有，反之亦然，则认为方案 $A$ 和方案 $B$ 是不同的。
回想一下，$k$ 个值 $x_1, x_2, \dots, x_k$ 的方差 $S^2$ 可以按如下方式计算： $$\bar{x} = \frac{x_1 + x_2 + \dots + x_k}{k}$$ $$S^2 = \frac{(x_1 - \bar{x})^2 + (x_2 - \bar{x})^2 + \dots + (x_k - \bar{x})^2}{k}$$
输入格式
每个测试输入文件中只有一组测试数据。
第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 40, 0 \le m \le \frac{n(n-1)}{2}$），表示城堡的数量和冲突关系的数量。
第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$（$0 \le w_i \le 2^{31} - 1$），表示每座城堡的防御值。
接下来的 $m$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n, x_i \neq y_i$），表示第 $x_i$ 座城堡和第 $y_i$ 座城堡不能同时装备大炮。
输出格式
输出单行一个整数，表示答案。如果答案为 $\frac{A}{B}$，请输出 $C$（$0 \le C < 10^9 + 7$），其中 $A \equiv C \times B \pmod{10^9 + 7}$。
样例
输入样例 1
3 1 1 2 3 1 2
输出样例 1
888888898
说明
| 装备大炮的城堡 | 防御值 | 装备大炮的城堡 | 防御值 |
|---|---|---|---|
| $\emptyset$ | $1$ | $\{3\}$ | $3$ |
| $\{1\}$ | $1$ | $\{1, 3\}$ | $3$ |
| $\{2\}$ | $2$ | $\{2, 3\}$ | $6$ |
因此答案为 $\frac{26}{9}$。由于 $9 \times 888888898 = 8000000082 \equiv 26 \pmod{10^9 + 7}$，我们输出 $888888898$。