Problem Description

Define the value of a bracket string as the number of pairs of matching brackets within it. This is the maximum number of times you can repeatedly remove a substring () from it.

You will encounter \( m \) bracket strings, where the length of the \( i \)-th string is \( l_i \). You can concatenate them in any order to form a single long bracket string, and your goal is to minimize the value of the resulting string.

If these \( m \) strings are generated with equal probability and your operation is optimal, please calculate the expected value of the final string's value. That is, you need to sum the minimum values for all possible initial bracket strings and then divide by \( 2^n \), where \( n \) is the total length of these strings. The result should be modulo \( 10^9+7 \).

Input Format

The first line contains an integer \( m \).

The second line contains \( m \) integers, representing \( l_1 \) to \( l_m \).

Output Format

A single integer representing the answer, modulo \( 10^9+7 \).

Sample Input and Output

Sample Input #1

2
2 2

Sample Output #1

62500001

Sample Input #2

5
1 2 3 4 5

Sample Output #2

762695321

Notes/Hints

[Sample Explanation 1]

Here, \(\{S_1, S_2\}\) represents an unordered multiset of two bracket strings, and \(P\) represents the probability of obtaining such a set.

The final answer is \(\frac{9}{16}\).

[Data Range]

Let \( n \) be the sum of \( 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 \).

见题面 Input 部分

见题面 Output 部分