题目描述

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, mod $(10^9+7)$.

对于由 $0$ 和 $1$ 组成的长度为 $N$ 的两个序列 $S$ 和 $T$ ，我们可以这样定义 $f(S, T)$ ：

• 考虑在 $S$ 上重复以下操作，使 $S$ 等于 $T$ 。 $f(S, T)$ 是这些操作可能的最小总成本。

  • 将 $S_i$ （从 $0$ 改为 $1$ ，反之亦然）。此操作的成本为 $D \times C_i$ ，其中 $D$ 是在此操作之前有 $j$ 的整数 $S_j \neq T_j (1 \leq j \leq N)$ 的个数。

有 $2^N \times (2^N - 1)$ 对长度为 $N$ 的不同序列 $(S, T)$ 由 $0$ 和 $1$ 组成。计算所有这些序列对中 $f(S, T)$ 的和，模为 $(10^9+7)$ 。

输入格式

输入内容按以下格式标准输入：

$N$
$C_1$ $C_2$ $\cdots$ $C_N$

输出格式

打印 $f(S, T)$ 的和，取模 $(10^9+7)$ .

样例 #1

样例输入 #1

1
1000000000

样例输出 #1

999999993

样例 #2

样例输入 #2

2
5 8

样例输出 #2

124

样例 #3

样例输入 #3

5
52 67 72 25 79

样例输出 #3

269312

说明

数据规模与约定

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq C_i \leq 10^9$
• 所有输入值均为整数。

样例 $1$ 解释

有两对长度为 $2$ 的不同序列 $(S, T)$ ，分别由 $0$ 和 $1$ 组成，如下所示：

• 将 $S = (0), T = (1):$ 中的 $S_1$ 改为 $1$ ，可以得到 $S = T$ ，代价是 $1000000000$ ，所以是 $f(S, T) = 1000000000$ 。
• $S = (1), T = (0):$ 将 $S_1$ 改为 $0$ ，可以得到 $S = T$ ，代价是 $1000000000$ ，所以是 $f(S, T) = 1000000000$ 。

这些值的总和是 $2000000000$ ，我们应该打印出它的模数 $(10^9+7)$ ，即 $999999993$ 。

样例 $2$ 解释

有 $12$ 对长度为 $3$ 的不同序列 $(S, T)$ 由 $0$ 和 $1$ 组成，其中包括

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

在这种情况下，如果我们先将 $S_1$ 改为 $1$ ，然后再将 $S_2$ 改为 $0$ ，则总成本为 $5 \times 2 + 8 = 18$ 。我们不可能以更小的代价得到 $S = T$ ，所以是 $f(S, T) = 18$ 。