威廉不仅对交易感兴趣,还对体育比赛投注感兴趣。 $$$n$$$ 队参加每场比赛。每个团队的特点都是实力$$$a_i$$$。每两支队伍 $$$i < j$$$ 彼此只玩一次。 $$$i$$$ 队获胜的概率为 $$$\frac{a_i}{a_i + a_j}$$$,$$$j$$$ 队获胜的概率为 $$$\frac{a_j}{a_i + a_j}$$$。
如果该团队直接或间接击败了所有其他团队,则该团队被称为获胜者。如果存在一系列团队 $$$c_1$$$、$$$c_2$$$、...$$$c_k$$$,使得 $$$c_1 = a$$$、$$$c_k = b$$$ 并且团队 $$$c_i$$$ 击败了团队 $$$c_{i + 1}$$$,则团队 $$$a$$$ 击败(直接或间接)团队 $$$b$$$ $$$i$$$ 从 $$$1$$$ 到 $$$k - 1$$$。请注意,$$$a$$$ 队有可能击败 $$$b$$$ 队,同时 $$$b$$$ 队也击败 $$$a$$$ 队。
William 希望您找到获胜者数量的预期值。
输入
第一行包含一个整数 $$$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}$$$。
示例
输入 #1
2 1 2
输出 #1
1
输入 #2
5 1 5 2 11 14
输出 #2
642377629
注意
为了更好地了解在什么情况下可能有多个获胜者,让我们检查第二个测试:
锦标赛的一种可能结果如下($$$a \rightarrow b$$$ 表示 $$$a$$$ 击败了 $$$b$$$):
- $$$1 \rightarrow 2$$$
- $$$2 \rightarrow 3$$$
- $$$3 \rightarrow 1$$$
- $$$1 \rightarrow 4$$$
- $$$1 \右箭头 5$$$
- $$$2 \rightarrow 4$$$
- $$$2 \右箭头 5$$$
- $$$3 \rightarrow 4$$$
- $$$3 \右箭头 5$$$
- $$$4 \右箭头 5$$$
或者在图片中更清楚:
在这种情况下,$$$\{ 1, 2, 3 \}$$$ 组中的每个团队都直接或间接击败了所有人。即:
- $$$1$$$st 打败了所有人,因为他们可以通过以下方式到达其他人 $$$1 \rightarrow 2$$$, $$$1 \rightarrow 2 \rightarrow 3$$$, $$$1 \rightarrow 4$$$, $$$1 \rightarrow 5$$$。
- $$$2$$$nd 打败了所有人,因为他们可以通过以下方式到达其他人 $$$2 \rightarrow 3$$$, $$$2 \rightarrow 3 \rightarrow 1$$$, $$$2 \rightarrow 4$$$, $$$2 \rightarrow 5$$$。
- $$$3$$$rd 击败了所有人,因为他们可以通过以下方式到达其他人 $$$3 \rightarrow 1$$$, $$$3 \rightarrow 1 \rightarrow 2$$$, $$$3 \rightarrow 4$$$, $$$3 \rightarrow 5$$$。
因此获奖者总数为$$$3$$$。