E - 稍微改变一下

分数：$500$ 点

问题描述

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

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

  • 改变 $S_i$ （从 $0$ 到 $1$，或者从 $1$ 到 $0$）。此操作的代价是 $D \times C_i$，其中 $D$ 是在这个改变之前对于所有 $1 \leq j \leq N$ 使得 $S_j \neq T_j$ 的整数的个数。

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

约束

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq C_i \leq 10^9$
• 输入中的所有值都是整数。

输入

输入从标准输入中以以下格式给出：

$N$

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

输出

输出 $f(S, T)$ 的总和，取模 $10^9+7$。

1
1000000000

999999993

存在 $2$ 对不同的由 $0$ 和 $1$ 组成且长度为 $2$ 的序列 $(S, T)$，如下：

• $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
5 8

124

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

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

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

5
52 67 72 25 79

269312