Bessie's Island Vacation

Bessie is vacationing on an island network consisting of \(N\) islands numbered \(1,2,\ldots,N\) and connected by \(M\) bidirectional bridges. Each bridge connects two distinct islands and the overall network is guaranteed to be connected and contains no multi‐edges or self-loops. Moreover, no bridge lies on more than one simple cycle (a cycle is a closed path that does not repeat any island).

Bessie starts her journey at island \(1\). When she is at island \(i\), let \(p_i\) (an integer between \(0\) and \(10^9+6\)) be given; interpret \(p_i\) as the probability (expressed in modulo \(10^9+7\) arithmetic) that she will end her vacation at island \(i\) immediately. The process works as follows:

1. If there is no bridge incident to island \(i\) that she has not yet traversed, then her vacation ends (she stops at \(i\)).
2. Otherwise, with probability \(p_i\) she ends her vacation on island \(i\).
3. If she does not stop, then among all bridges incident to island \(i\) that she has not yet traversed, she chooses one uniformly at random and crosses it. Note that once a bridge is crossed it cannot be used again.

Your task is: given the graph and the values \(p_1, p_2, \ldots, p_N\), compute for each island the probability that Bessie ends her vacation on that island. All probabilities are to be computed in modulo \(10^9+7\) (where \(1\) is represented by the integer \(1\), and the fraction \(\tfrac{1}{2}\) is represented by \(500000004\), etc.).

Input Constraints:

• \(2 \le N \le 10^4\).
• \(N-1 \le M \le \frac{3(N-1)}{2}\).
• The graph is simple and connected, and no bridge may lie on more than one simple cycle.

Note: It is guaranteed that Bessie's journey will eventually stop.

inputFormat

The first line contains two integers \(N\) and \(M\). The second line contains \(N\) integers \(p_1, p_2, \ldots, p_N\), where each \(p_i\) is given in the range \([0,10^9+6]\) and represents the stopping probability at island \(i\) in modulo \(10^9+7\) (i.e. a value of \(500000004\) corresponds to \(\frac{1}{2}\)). Each of the next \(M\) lines contains two integers \(u\) and \(v\), indicating that there is a bidirectional bridge connecting islands \(u\) and \(v\).

outputFormat

Output a single line containing \(N\) integers. The \(i\)th integer is the probability (in modulo \(10^9+7\)) that Bessie ends her vacation on island \(i\).

sample

2 1
500000004 0
1 2

500000004 500000004