Noclipping is a temporal phasing that allows one to bypass the normal boundaries of spatial reality. Urban legends suggest that once you noclip out of reality, you'll end up in the backrooms.
Unfortunately for Moussa, he wasn't careful and he noclipped into the backrooms. Luckily, he read the online threads and watched the footages. He knows that the backrooms consists of $$$n$$$ rooms numbered from $$$1$$$ to $$$n$$$, there are $$$m$$$ passages where the $$$i$$$-th passage links the rooms $$$a_i$$$ and $$$b_i$$$. In simpler words, the backrooms are a connected undirected graph.
Moussa is currently at room $$$1$$$ and he needs to reach room $$$n$$$. He can go through any passage in $$$1$$$ second. As all of the backrooms look the same, Moussa's approach is whenever he is in room $$$u$$$, he will use any passage to go to any other room. The passage is chosen randomly. More formally, if Moussa is currently at room $$$u$$$ that has $$$x$$$ passages, he will use a random passage with probability $$$\frac{1}{x}$$$ to go to another room and so on until he reaches room $$$n$$$.
Moussa knows that each room from $$$2$$$ to $$$n-1$$$ has exactly one monster. Once Moussa enters a room $$$i$$$ that has a monster, the monster have probability $$$p_i$$$ to be asleep and probability $$$1-p_i$$$ to be awake. If the monster is asleep, Moussa will leave the room peacefully. If the monster is awaken, Moussa is in no danger because as a minecraft expert, he knows how to craft a potion using no material and kill the monster in $$$2$$$ seconds, then he can leave the room to another room. Once a monster is killed, he will be dead until the end of the journey.
Moussa is already terrified being in the backrooms. He wants to find the expected number of seconds he will need to leave the backrooms so he can continue working on the problems you are solving right now. He cannot waste any time finding the value, so can you find it instead?
The first line of the input contains two space-separated integer numbers $$$n$$$ and $$$m$$$ $$$(2 \le n \le 17, n-1 \le m \le \frac{n \times (n-1)}{2})$$$. The number of rooms and the number of passages in the backrooms, respectively.
The next line of the input contains $$$n-2$$$ space-separated probabilities, where the $$$i$$$-th probability is the probability of the monster in the $$$i+1$$$-th room being asleep. The probability is given in the format $$$p/q$$$ $$$(0 \le p \le 10^9, 1 \le q \le 10^9, p \le q)$$$. It is guaranteed that $$$p$$$ and $$$q$$$ are coprime. If $$$n=2$$$, the line will be empty.
The next $$$m$$$ lines each contains two space-separated integer numbers $$$a_i$$$ and $$$b_i$$$ $$$(1 \le a_i, b_i \le n, a_i \ne b_i)$$$, denoting having a passage between room $$$a_i$$$ and room $$$b_i$$$.
It is guaranteed that the input forms a connected graph with no self loops or multiple edges.
Print a single integer. The expected number of seconds he will need to leave the backrooms.
It can be shown that it is in the form of $$$\frac{p}{q}$$$ where $$$p$$$ and $$$q$$$ are non-negative integers and $$$q \ne 0$$$. Report the value of $$$p \times q^{-1}\ mod (10^9+7)$$$.
3 3 1/2 1 2 2 3 1 3
571428578
