稍作修改

题目描述

对于由 $0, 1$ 组成的长为 $N$ 的两个不同数列 $S, T$,定义函数 $f(S, T)$ 如下:

• 考虑对 $S$ 重复执行以下操作使其与 $T$ 相同。此时操作成本之和的最小可能值即为 $f(S, T)$。

操作:将 $S_i$ 改为(从 $0$ 变为 $1$,或从 $1$ 变为 $0$)。设操作前满足 $S_j \neq T_j (1 \leq j \leq N)$ 的整数 $j$ 的个数为 $D$,则此操作的成本为 $D \times C_i$。

由 $0, 1$ 组成的长为 $N$ 的两个不同数列的组 $(S, T)$ 共有 $2^N \times (2^N - 1)$ 种。请计算所有这些组对应的 $f(S, T)$ 之和除以 $10^9+7$ 的余数。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出 $f(S, T)$ 之和除以 $10^9+7$ 的余数。

样例

1
1000000000

999999993

由 $0, 1$ 组成的长为 $1$ 的两个不同数列的组 $(S, T)$ 有以下 $2$ 种:

• $S = (0), T = (1):$ 将 $S_1$ 改为 $1$,可以用成本 $1000000000$ 使 $S = T$,因此 $f(S, T) = 1000000000$。
• $S = (1), T = (0):$ 将 $S_1$ 改为 $0$,可以用成本 $1000000000$ 使 $S = T$,因此 $f(S, T) = 1000000000$。

这些之和为 $2000000000$,除以 $10^9+7$ 的余数为 $999999993$。

2
5 8

124

由 $0, 1$ 组成的长为 $2$ 的两个不同数列的组 $(S, T)$ 共有 $12$ 种,例如有以下情况:

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

此时,如果第 $1$ 次操作将 $S_1$ 改为 $1$,第 $2$ 次操作将 $S_2$ 改为 $0$,则操作成本之和为 $5 \times 2 + 8 = 18$。不存在成本更小的方案能使 $S = T$,因此 $f(S, T) = 18$。

5
52 67 72 25 79

269312

数据范围

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