
ZOJ Problem Set  4098
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 cannonarmed 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} $$ InputThere 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(n1)}{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. OutputOutput 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 Input3 1 1 2 3 1 2 Sample Output888888898 Hint
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 