Home

Problem Statement

For two sequences $S$ and $T$ of length $N$ consisting of $0$ and $1$, let us define $f(S, T)$ as follows:

• Consider repeating the following operation on $S$ so that $S$ will be equal to $T$. $f(S, T)$ is the minimum possible total cost of those operations.

  • Change $S_i$ (from $0$ to $1$ or vice versa). The cost of this operation is $D \times C_i$, where $D$ is the number of integers $j$ such that $S_j \neq T_j (1 \leq j \leq N)$ just before this change.

There are $2^N \times (2^N - 1)$ pairs $(S, T)$ of different sequences of length $N$ consisting of $0$ and $1$. Compute the sum of $f(S, T)$ over all of those pairs, modulo $(10^9+7)$.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq C_i \leq 10^9$
• All values in input are integers.

Sample Input 1

1
1000000000

Sample Output 1

999999993

There are two pairs $(S, T)$ of different sequences of length $2$ consisting of $0$ and $1$, as follows:

• $S = (0), T = (1):$ by changing $S_1$ to $1$, we can have $S = T$ at the cost of $1000000000$, so $f(S, T) = 1000000000$.
• $S = (1), T = (0):$ by changing $S_1$ to $0$, we can have $S = T$ at the cost of $1000000000$, so $f(S, T) = 1000000000$.

The sum of these is $2000000000$, and we should print it modulo $(10^9+7)$, that is, $999999993$.

Sample Input 2

2
5 8

Sample Output 2

124

There are $12$ pairs $(S, T)$ of different sequences of length $3$ consisting of $0$ and $1$, which include:

• $S = (0, 1), T = (1, 0)$

In this case, if we first change $S_1$ to $1$ then change $S_2$ to $0$, the total cost is $5 \times 2 + 8 = 18$. We cannot have $S = T$ at a smaller cost, so $f(S, T) = 18$.

Sample Input 3

5
52 67 72 25 79

Sample Output 3

269312