P10896 Yiyan Dingzhen: Unavoided linyue

**Note: You do not need to read the background of this problem.** "$\textsf{linyue}$" is the only personal name I have ever used, so $\textsf{linyue}$ became the only character I have ever imagined. She is the protagonist of all the stories in my mind, and she is very important to me. So important that, for some reason, every time I see her name written down or hear it spoken, I feel at a loss. Therefore I always try to avoid it. For example, in this problem statement I use pinyin as a substitute. When I first learned about a game called “TRPG (跑团, paotuan)”, I was basically “desperately wanting to play anything with anyone”. But the pandemic ruined many of my plans to play with classmates, so I was even forced to consider it in my plans. However, since it was really too complicated, I soon threw it out of my mind. “Black Shadow Kill (黑影杀, heiyingsha)” is a game that became popular in the official chat group of *Wings of Ningzhi (泞之翼)*. Players explore the hotel from the original *Wings of Ningzhi* story, avoiding shadows to escape alive—there is nothing more perfect than this for me. It completely fulfills my wish in the previous paragraph: whenever I have time, I can “start the slaughter” in the group. I prepared a host-friendly program for this game, wrote many special rules, and even made problems based on it—although the contest I submitted this problem to got canceled. *Monster Merchant One Carat (怪商一克拉)* is a manga I really like. Its special trait is that the protagonist seems to complete the task in each story only to the smallest extent, and then, even if there are many unsolved mysteries, it just jumps to the next story. Although this looks like poor writing, I believe the author did it on purpose. So I looked forward to seeing these foreshadowings solved cleverly in the future, leading to a shocking ending. But one day, I did not see this manga at the manga party. That meant none of the above would ever happen... I broke down for a long time, and I even went crazy in the *Wings of Ningzhi* group. But in fact, the author just took a one-month break, and the manga would continue updating as usual. A couple of days ago, I finally found a chance to go out and have fun with classmates again. This time we planned to visit a shop that mainly runs Mirrorland TRPG (镜土 TRPG) and try playing. You should know that this is still very attractive to me, because before, no matter what I played, it was always “me” playing, and it had nothing to do with $\textsf{linyue}$. But if we play TRPG and make a character sheet, could it fill this regret? So this time I came prepared. I worked hard in advance to draw a simple picture of $\textsf{linyue}$. Then, when entering the name, I decided not to avoid it anymore—using her real name in two Chinese characters, rather than the six-letter substitute. However, although that day I heard and saw her name more times than ever before, it did not have a very good effect in the end. In the game, I was indeed completely not immersed. My dialogues had an “average of all humanity” kind of beauty. I did not reason out any key part of the plot, and I did not come up with any novel ideas. Replacing me with Kimi AI would definitely make the game more interesting... —But of course, this was also expected, because I know I am really, really bad at this kind of role-playing... It seems that, for me, creating stories for $\textsf{linyue}$ is harder than it is for others. So I will not be too bothered by this problem: first, because I am used to it; second, because—our contest by the problem-setting team did not pass the review.  “Yiyan Dingzhen” was originally planned as one of the Problem E of this contest, but it was judged as a classic... Clearly, this is mainly my fault. So my top priority now is to come up with a new idea...

Define the value of a bracket string as the number of bracket pairs that can be matched. That is, you repeatedly delete some substring equal to ```()``` from it, and the value is the maximum number of deletions you can perform. You will be given $m$ bracket strings, where the length of the $i$-th string is $l_i$. You may concatenate them in any order to form one long bracket string, and your goal is to minimize the value of the final string. If these $m$ strings are generated uniformly at random, and your operation is optimal, compute the expected value of the final value. That is, for all possible initial bracket strings, compute the sum of the minimal values and then divide by $2^n$, where $n$ is the total length of these strings. Output the result modulo $10^9+7$.

The first line contains an integer $m$. The second line contains $m$ integers, representing $l_1$ to $l_m$.

Output one integer, the answer modulo $10^9+7$.

**Sample Explanation 1** Here $\{S_1,S_2\}$ denotes an unordered multiset consisting of two bracket strings, and $P$ denotes the probability of getting such a multiset. | $\{S_1,S_2\}$ | $P$ | Optimal plan | Value | | :-----------: | :-----------: | :-----------: | :-----------: | | $\{$```((```$,$```((```$\}$ | $\frac{1}{16}$ | ```((((``` | $0$ | | $\{$```((```$,$```()```$\}$ | $\frac{1}{8}$ | Any | $1$ | | $\{$```((```$,$```)(```$\}$ | $\frac{1}{8}$ | ```)(((``` | $0$ | | $\{$```((```$,$```))```$\}$ | $\frac{1}{8}$ | ```))((``` | $0$ | | $\{$```()```$,$```()```$\}$ | $\frac{1}{16}$ | ```()()``` | $2$ | | $\{$```()```$,$```)(```$\}$ | $\frac{1}{8}$ | Any | $1$ | | $\{$```()```$,$```))```$\}$ | $\frac{1}{8}$ | Any | $1$ | | $\{$```)(```$,$```)(```$\}$ | $\frac{1}{16}$ | ```)()(``` | $1$ | | $\{$```)(```$,$```))```$\}$ | $\frac{1}{8}$ | ```)))(``` | $0$ | | $\{$```))```$,$```))```$\}$ | $\frac{1}{16}$ | ```))))``` | $0$ | The final answer is $\dfrac{9}{16}$. **Constraints** Let $n$ be the sum of all $l_i$. Subtask $1$ ($20$ points): $n \le 20$. Subtask $2$ ($30$ points): $n \le 5000$. Subtask $3$ ($50$ points): $n \le 4000000$. It is guaranteed that $l_i \ge 1$. **Postscript** A left bracket and a right bracket can be the first and second characters of $\textsf{linyue}$’s name, or they can be the beginning and the outcome of a story. The next TRPG session is nowhere in sight, Black Shadow Kill is gradually being forgotten, and the three originally planned Problem E tasks of our team, along with many other ideas, do not know where they will go. Stories and concepts related to $\textsf{linyue}$ are even harder to present. Sometimes I feel like I am in *Monster Merchant One Carat*: many parts of my experiences have not waited for their right bracket, and they have a kind of beauty of having their value minimized. So I always look forward to these foreshadowings being solved cleverly, bringing the greatest happiness. But before that, I can only keep avoiding “$\textsf{linyue}$”. Translated by ChatGPT 5