Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

combinatorics

dp

graphs

math

probabilities

*2500

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Sports Betting

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputWilliam 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

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

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

Examples

Input

2 1 2

Output

1

Input

5 1 5 2 11 14

Output

642377629

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/14/2024 08:12:02 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|