CF1556F.Sports Betting

William is not only interested in trading but also in betting on sports matches. $n$ teams participate in each match. Each team is characterized by strength $a_i$. Each two teams $i \lt j$ play with each other exactly once. Team $i$ wins with probability $\frac{a_i}{a_i + a_j}$ and team $j$ wins with probability $\frac{a_j}{a_i + a_j}$.

The team is called a winner if it directly or indirectly defeated all other teams. Team $a$ defeated (directly or indirectly) team $b$ if there is a sequence of teams $c_1$, $c_2$, ... $c_k$ such that $c_1 = a$, $c_k = b$ and team $c_i$ defeated team $c_{i + 1}$ for all $i$ from $1$ to $k - 1$. Note that it is possible that team $a$ defeated team $b$ and in the same time team $b$ defeated team $a$.

William wants you to find the expected value of the number of winners.

威廉不仅对交易感兴趣，也热衷于对体育比赛下注。每场比赛有 $n$ 支队伍参赛。每支队伍 $i$ 由其实力值 $a_i$ 刻画。任意两支队伍 $i < j$ 恰好进行一场比赛。其中队伍 $i$ 获胜的概率为 $\frac{a_i}{a_i + a_j}$，队伍 $j$ 获胜的概率为 $\frac{a_j}{a_i + a_j}$。

若一支队伍能直接或间接击败所有其他队伍，则称该队伍为“胜者”。我们称队伍 $a$ 击败（直接或间接） 队伍 $b$，当且仅当存在一个队伍序列 $c_1, c_2, \dots, c_k$，满足 $c_1 = a$、$c_k = b$，且对每个 $i = 1, 2, \dots, k-1$，队伍 $c_i$ 击败了队伍 $c_{i+1}$。注意：可能存在队伍 $a$ 击败队伍 $b$，同时队伍 $b$ 也击败队伍 $a$ 的情况（即存在环）。

威廉希望你计算胜者数量的期望值。

The first line contains a single integer $n$ ($1 \leq n \leq 14$), which is the total number of teams participating in a match.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^6$) — the strengths of teams participating in a match.

第一行包含一个整数 $n$（$1 \leq n \leq 14$），表示参加比赛的队伍总数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^6$）—— 表示参加比赛的各支队伍的实力。

Output a single integer — the expected value of the number of winners of the tournament modulo $10^9 + 7$.

Formally, let $M = 10^9+7$. It can be demonstrated that the answer can be presented as a irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output a single integer equal to $p \cdot q^{-1} \bmod M$. In other words, output an integer $x$ such that $0 \le x \lt M$ and $x \cdot q \equiv p \pmod{M}$.

输出一个整数——该锦标赛获胜者人数的期望值对 $10^9 + 7$ 取模的结果。

形式化地，令 $M = 10^9+7$。可以证明答案可表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not \equiv 0 \pmod{M}$。请输出一个整数，其值等于 $p \cdot q^{-1} \bmod M$。换言之，输出一个整数 $x$，满足 $0 \le x \lt M$ 且 $x \cdot q \equiv p \pmod{M}$。

To better understand in which situation several winners are possible let's examine the second test:

One possible result of the tournament is as follows ($a \rightarrow b$ means that $a$ defeated $b$):

• $1 \rightarrow 2$
• $2 \rightarrow 3$
• $3 \rightarrow 1$
• $1 \rightarrow 4$
• $1 \rightarrow 5$
• $2 \rightarrow 4$
• $2 \rightarrow 5$
• $3 \rightarrow 4$
• $3 \rightarrow 5$
• $4 \rightarrow 5$

Or more clearly in the picture:

In this case every team from the set ${ 1, 2, 3 }$ directly or indirectly defeated everyone. I.e.:

• $1$st defeated everyone because they can get to everyone else in the following way $1 \rightarrow 2$, $1 \rightarrow 2 \rightarrow 3$, $1 \rightarrow 4$, $1 \rightarrow 5$.
• $2$nd defeated everyone because they can get to everyone else in the following way $2 \rightarrow 3$, $2 \rightarrow 3 \rightarrow 1$, $2 \rightarrow 4$, $2 \rightarrow 5$.
• $3$rd defeated everyone because they can get to everyone else in the following way $3 \rightarrow 1$, $3 \rightarrow 1 \rightarrow 2$, $3 \rightarrow 4$, $3 \rightarrow 5$.

Therefore the total number of winners is $3$.

为了更好地理解在哪些情况下可能存在多个获胜者，我们来分析第二个测试用例：

该锦标赛的一种可能结果如下（其中 $a \rightarrow b$ 表示 $a$ 击败了 $b$）：

• $1 \rightarrow 2$
• $2 \rightarrow 3$
• $3 \rightarrow 1$
• $1 \rightarrow 4$
• $1 \rightarrow 5$
• $2 \rightarrow 4$
• $2 \rightarrow 5$
• $3 \rightarrow 4$
• $3 \rightarrow 5$
• $4 \rightarrow 5$

或者更清晰地表示为下图：

在此情形下，集合 $\{ 1, 2, 3 \}$ 中的每支队伍均直接或间接击败了所有其他队伍。即：

• 第 $1$ 支队伍击败了所有人，因为其可通过如下路径到达其余所有队伍：$1 \rightarrow 2$、$1 \rightarrow 2 \rightarrow 3$、$1 \rightarrow 4$、$1 \rightarrow 5$。
• 第 $2$ 支队伍击败了所有人，因为其可通过如下路径到达其余所有队伍：$2 \rightarrow 3$、$2 \rightarrow 3 \rightarrow 1$、$2 \rightarrow 4$、$2 \rightarrow 5$。
• 第 $3$ 支队伍击败了所有人，因为其可通过如下路径到达其余所有队伍：$3 \rightarrow 1$、$3 \rightarrow 1 \rightarrow 2$、$3 \rightarrow 4$、$3 \rightarrow 5$。

因此，获胜者总数为 $3$。