F. Ставки на матчи
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Василий увлекается не только трейдингом, но и ставками на спортивные матчи. В матче участвует $$$n$$$ спортивных команд. Каждая команда характеризуется силой $$$a_i$$$. Каждые две команды $$$i < j$$$ играют друг с другом ровно один раз. С вероятностью $$$\frac{a_i}{a_i + a_j}$$$ побеждает команда $$$i$$$, с вероятностью $$$\frac{a_j}{a_i + a_j}$$$ побеждает команда $$$j$$$.

Команда называется победителем, если она прямо или косвенно победила все остальные команды. Команда $$$a$$$ победила (прямо или косвенно) команду $$$b$$$, если существует последовательность команд $$$c_1$$$, $$$c_2$$$, ... $$$c_k$$$ такая, что $$$c_1 = a$$$, $$$c_k = b$$$ и команда $$$c_i$$$ выиграла матч у команды $$$c_{i + 1}$$$ для всех $$$i$$$ от $$$1$$$ до $$$k - 1$$$. Обратите внимание, что возможно, что команда $$$a$$$ победила команду $$$b$$$, и в то же время команда $$$b$$$ победила команду $$$a$$$.

Василий хочет, чтобы вы помогли ему определить математическое ожидание количества победителей.

Входные данные

В первой строке находится целое число $$$n$$$ ($$$1 \leq n \leq 14$$$) — количество команд, участвующих в матче.

В следующей строке находится $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$) — силы команд, участвующих в матче.

Выходные данные

Выведите единственное целое число — математическое ожидание количества победителей турнира по модулю $$$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 < M$$$ и $$$x \cdot q \equiv p \pmod{M}$$$.

Примеры
Входные данные
2
1 2
Выходные данные
1
Входные данные
5
1 5 2 11 14
Выходные данные
642377629
Примечание

Чтобы лучше понять, в каких ситуациях возможно несколько победителей, рассмотрим второй тест:

Одним из возможных результатов сыгранных матчей является следующий ($$$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$$$.