题目背景

注：你不需要阅读此题题目背景。

"$\textsf{linyue}$" 是我起过的唯一一个人名，所以 $\textsf{linyue}$ 成了唯一一个由我想象出来的角色。她是我脑海中所有故事的主角，对我而言非常地重要，以至于不知道为什么，每次我看到她的名字被写出来或是被读出来都会感到无所适从，所以我总是会想办法避免这样，比如说这个题的题面里我就用的是拼音作代替。

“跑团”这种游戏我最初了解的时候简直是“绝望地想要跟不管是谁玩随便什么”。可是疫情却让我的好多和同学玩的计划纷纷泡汤，所以我甚至走投无路到把它也纳入了计划的考虑范畴，不过由于它实在是太复杂了，没过多久我就把它抛诸脑后了（

“黑影杀”是一款在泞之翼官方交流群里兴起的游戏，玩家将会探索《泞之翼》原作的旅馆，躲避黑影以求逃出生天——对我而言没有比这更完美的事了！它完全实现了我上一段里的愿望，只要一有空，我便可以在群里“开鲨”！我给这个游戏准备了便于主持的程序，写了许多特殊规则，甚至还以它为背景出了题——尽管这题投到的比赛咕了（

《怪商一克拉》是一部我很喜欢的漫画。它的特点就是主角好像在每段故事里都只会最小程度地完成任务，然后哪怕这个故事还有好多未解之谜都只会跳到下一段故事。尽管这看起来像是没写好，但我相信这种效果作者是刻意为之。所以我期待着在未来看到这些故事的伏笔被精妙地解决，带来一个震撼的结局。可是有一天，我没有在漫画派对上看到这部漫画。这意味着以上就都不会发生了……我当时心态崩了好长时间，甚至都到泞之翼群里发癫了，不过事实上作者只是请了一个月假，接下来这漫画还会照常更新（

前两天，我终于又找到机会和同学出去玩了！这一次我们打算上一个主营镜土 TRPG 的店里试试跑团。要知道，这对我而言还是很有吸引力的，因为之前不管是玩什么，都是"我"在玩，跟 $\textsf{linyue}$ 没有什么关系。但要是玩跑团做角色卡的话，是不是就能填补这个遗憾了呢？所以这次我是有备而来！我提前十分费力地给 $\textsf{linyue}$ 画了一张简单的画，然后输入名字的时候，我决定不再回避——用她那两个汉字的真名，而非六个字母的替代。

然而，尽管我这一天听到和看到她名字的次数前所未有，但最后却并没什么很好的效果。我在游戏里确实是主打一个不入戏，对话内容有种全人类取平均的美，没推理出什么剧情的关键，也没想到什么新奇的点子。相信把我换成 Kimi AI 游戏绝对会更有趣……

——不过当然啦，这倒也在我意料之中，因为我知道我本来就非常非常不擅长这种角色扮演……看来对我而言，创造 $\textsf{linyue}$ 的故事会比别人更加困难。

所以我不会太受这个问题的困扰，一是因为习惯了，二是因为——我们出题组的比赛没过审。

“移言丁真”是这场比赛的原定 E 题之一，可是它被鉴定为了典……显然这最主要是我的锅。所以我现在的当务之急是要想一个新的 idea……

题目描述

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

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

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

输入格式

第一行一个整数 $m$。

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

输出格式

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

2
2 2

62500001

5
1 2 3 4 5

762695321

提示

【样例解释1】

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

$\{S_1,S_2\}$	$P$	最优方案	权值
$\{$(($,$(($\}$	$\frac{1}{16}$	((((	$0$
$\{$(($,$()$\}$	$\frac{1}{8}$	任意	$1$
$\{$(($,$)($\}$		)(((	$0$
$\{$(($,$))$\}$		))((
$\{$()$,$()$\}$	$\frac{1}{16}$	()()	$2$
$\{$()$,$)($\}$	$\frac{1}{8}$	任意	$1$
$\{$()$,$))$\}$
$\{$)($,$)($\}$	$\frac{1}{16}$	)()(
$\{$)($,$))$\}$	$\frac{1}{8}$	)))(	$0$
$\{$))$,$))$\}$	$\frac{1}{16}$	))))

最终答案为 $\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}$” 了。