Sports Betting
Contest: Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2)
Difficulty rating: 2500
Tags: bitmasks, combinatorics, dp, graphs, math, probabilities

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 < 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.

Input format:
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.

Output format:
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 < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
2
1 2

Example output:
1

Example input:
5
1 5 2 11 14

Example output:
642377629

Editorial:
Let $$$ALL$$$ be all teams, and $$$F(winners)$$$ be the probability that a set of $$$winners$$$ teams are winners, and the rest of $$$ALL \setminus winners$$$ teams are not.
Then the answer will be the following value:
$$$$$$ \sum_{winners \neq \varnothing, winners \subseteq ALL} F(winners) \cdot |winners| $$$$$$
Let's define extra value:
$$$P(winners)$$$ — the probability that all teams from the set $$$winners$$$ are reachable from each other, that is, they form a cycle.
Then $$$F$$$ is calculated as follows: $$$F(winners) = P(winners) \cdot G(winners, ALL \setminus winners)$$$.
This is explained as follows: the probability that the set $$$winners$$$ will be the set of winners is equal to the probability that the set $$$winners$$$ forms a cycle and there is no edge from the set $$$ALL \setminus winners$$$ to $$$winners$$$.
Where $$$G(X, Y)$$$ denotes the probability that all teams from the set $$$X$$$ defeat all teams from the set $$$Y$$$ directly. More formally speaking, the probability that for every $$$x$$$ in $$$X$$$, and for every $$$y$$$ in $$$Y$$$, there is an edge from $$$x$$$ to $$$y$$$.
It remains to learn how to count $$$P(winners)$$$.
It is easy to see that this can be done using the inclusion-exclusion principle:
$$$$$$ P(winners) = 1 - \sum_{sub \subset winners, sub \neq winners} P(sub) \cdot G(sub, winners \setminus sub) $$$$$$
The formula is explained as follows: we need to know the probability that all teams from the set $$$winners$$$ are reachable to each other, initially we set this probability equal to $$$1$$$, then subtract all options when only some subset $$$sub$$$ of the set $$$winners$$$ is reachable to itself.
$$$G(X, Y)$$$ is calculated as follows:
$$$$$$ G(X, Y) = \prod_{x \in X, y \in Y} \frac{a_x}{a_x + a_y} $$$$$$
Writing these formulas into the code in the simplest way, you can get a solution with asymptotics $$$O(3^{N} \cdot N^2)$$$. Since here $$$O(3^N)$$$ pairs $$$(winners, sub)$$$ exist, where $$$winners$$$ is the set of winners and $$$sub$$$ is its subset in the inclusion-exclusion formula. Also, for each such pair, you will have to calculate the value of $$$G(sub, winners \setminus sub)$$$ in $$$O(N^2)$$$.
But it is possible to calculate $$$G(X, Y)$$$ faster.
For example, you can notice that $$$G(X, Y) = \prod_ {x \in X} H(x, Y)$$$, where $$$H(x, Y)$$$ is the probability that the command $$$x$$$ defeated all teams from the set $$$Y$$$ directly. $$$H$$$ can be pre-calculated in advance for $$$O(2^N \cdot N)$$$, which will allow us to calculate $$$G(X, Y)$$$ in $$$O(N)$$$ instead of $$$O(N^2)$$$.
In a similar way, you can learn how to calculate $$$G(X, Y)$$$ in $$$O(1)$$$, if you pre-calculate the following four values: $$$G_{left, left}(X, Y)$$$, $$$G_{left, right}(X, Y)$$$, $$$G_{right, left}(X, Y)$$$, $$$G_{right, right}(X, Y)$$$.
Where $$$left, right$$$ is an arbitrary division of teams into two equal (or almost equal) sets, so that $$$||left| - |right|| \leq 1$$$ is satisfied.
Where $$$G_{side_{from}, side_{to}}(X, Y) = G(X, Y)$$$, only for subsets such that $$$X \subseteq side_{from}, Y \subseteq side_{to}$$$.
As a result:
$$$$$$ G(X, Y) = \prod_{side_{from} \in \{ left, right \} } \prod_{side_{to} \in \{ left, right \} } G_{side_{from}, side_{to}}(X \cap side_{from}, Y \cap side_{to}) $$$$$$
Each of $$$G_{side_{from}, side_{to}}$$$ can be pre-calculated in $$$O(2^N \cdot N)$$$.
Final asymptotics $$$O(3^N)$$$.