Welcome to ZOJ
Select Problem
ZOJ Problem Set - 4098
Defense Plan

Time Limit: 1 Second      Memory Limit: 262144 KB

Potato Kingdom is about to be attacked by the evil Heltion Kingdom! As the Secretary of Defense, Little Sub must arrange the defense system very carefully.

There are $n$ castles in Potato Kingdom in total and Little Sub is planning to equip some of them with cannons. However, if two castles are too close to each other, they cannot be both cannon-armed since they might hurt each other.

The $i$-th castle has a defense value of $w_i$. Let $\mathbb{C}$ be the set of the \textbf{index} of all castles armed with cannons, we define the total defense value to be $$\prod\limits_{k \in \mathbb{C}}w_k$$ For completeness, if $\mathbb{C} = \emptyset$, the total defense value is defined to be 1.

There are many possible plans to equip cannons to these castles and Little Sub must choose a proper one. In order to value the situation correctly and more precisely, he wants to know about the variance $S^{2}$ of all feasible plan's total defense value (note that arming no castle with cannons is also a feasible plan). Two plans A and B are considered to be different if a castle is armed with cannons in plan A but not in plan B, or vice versa.

Recall that the variance $S^2$ of $k$ values $x_1, x_2, \dots, x_k$ can be calculated as follows: $$ \bar{x}=\frac{x_{1}+x_{2}+...+x_{k}}{k} \qquad S^{2}=\frac{ (x_{1}-\bar{x} )^{2}+(x_{2}-\bar{x} )^{2}+...+(x_{k}-\bar{x} )^{2} }{k} $$


There will be only one test case in each test file (and of course we have prepared multiple test files).

The first line contains two integers $n$ and $m$ ($1 \le n \le 40, 0 \le m \le \frac{n(n-1)}{2}$), indicating the number of castles and conflict relations.

The second line contains $n$ integers $w_1, w_2, \dots, w_n$ ($0 \le w_i \le 2^{31} - 1$), indicating the defense value of castles.

For the following $m$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$, $x_i \ne y_i$), indicating that the $x_i$-th and the $y_i$-th castle cannot be both armed with cannons.


Output a single integer in a single line, indicating the answer. If the answer is $\frac{A}{B}$, please print $C(0\leq C<10^9+7)$ where $A\equiv C\times B\pmod{10^9+7}$.

Sample Input

3 1
1 2 3
1 2

Sample Output



Castles Armed Defense Value Castles Armed Defense Value
{} 1 {3} 3
{1} 1 {1, 3} 3
{2} 2 {2, 3} 6

So the answer is $\frac{26}{9}$. As $9 \times 888888898 = 8000000082 \equiv 26 \pmod{10^9 + 7}$, we print 888888898.

Author: CHEN, Jingbang
Source: The 19th Zhejiang University Programming Contest Sponsored by TuSimple
Submit    Status