Василий увлекается не только трейдингом, но и ставками на спортивные матчи. В матче участвует \(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\).
Василий хочет, чтобы вы помогли ему определить математическое ожидание количества победителей.
Выходные данные
Выведите единственное целое число — математическое ожидание количества победителей турнира по модулю \(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}\).
Примечание
Чтобы лучше понять, в каких ситуациях возможно несколько победителей, рассмотрим второй тест:
Одним из возможных результатов сыгранных матчей является следующий (\(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 2
|
1
|
|
2
|
5
1 5 2 11 14
|
642377629
|