Description

定义一个括号串的权值为其中可配对的括号组数。也就是你重复地在里面删除掉某个为 () 的子串，最多可以删除的次数。

你会遇到 $m$ 个括号串，第 $i$ 个的长度是 $l_i$。你可以将它们按照任意顺序连接起来，然后连成一个长的括号串，而你的目标就是让最终的串的权值最小。

如果这 $m$ 个串是等概率随机生成的，而你的操作是最优的，请你求出最终权值的期望。也就是说你要对于初始括号串的所有可能性求出最小权值的和再除以 $2^n$，$n$ 为这些字符串的总长。对 $10^9+7$ 取模。

Input Format

第一行一个整数 $m$。

第二行 $m$ 个整数，表示 $l_1$ 到 $l_m$。

Output Format

一行一个整数表示答案，对 $10^9+7$ 取模。

2
2 2

62500001

5
1 2 3 4 5

762695321

Hint

【样例解释1】

这里 $\{S_1,S_2\}$ 表示两个括号串构成的无序可重集合，$P$ 表示取到这样集合的概率。

最终答案为 $\dfrac{9}{16}$。

【数据范围】

令 $n$ 为 $l_i$ 的总和。

子任务 $1$（$20$ 分）: $n \le 20$。

子任务 $2$（$30$ 分）: $n \le 5000$。

子任务 $3$（$50$ 分）: $n \le 4000000$。

保证 $l_i \ge 1$。

【后记】

左括号和右括号可以是 $\textsf{linyue}$ 名字的第一个字和第二个字，也可以是一段故事的萌芽和结果。

下一次跑团遥遥无期，黑影杀渐渐无人问津，我们团的三个原定 E 题和其他好多好多的 idea 不知道何去何从，那些和 $\textsf{linyue}$ 有关的故事和设想更是也难以被呈现。有时我感觉自己就像是在《怪商一克拉》里一样，好多段经历都没等到自己的右括号，有种被最小化了权值的美。所以，我总是期待这些故事的伏笔被精妙地解决，带来最大的幸福。不过在这之前，我只好继续回避 “$\textsf{linyue}$” 了。