问题描述

对于长度为 $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$ 是在该改变之前，$S_j \neq T_j$（$1 \leq j \leq N$）的整数 $j$ 的数量。

计算所有不同的长度为 $N$ 的由 $0$ 和 $1$ 组成的序列对 $(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

1
1000000000

示例输出 1

999999993

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

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

2
5 8

示例输出 2

124

对于长度为 $3$ 的由 $0$ 和 $1$ 组成的序列，有 $12$ 对不同的序列 $(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$。

示例输入 3

5
52 67 72 25 79

示例输出 3

269312