题目描述

对于两个长度为 $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$。

输入

第一行一个整数$N$

第二行一共$N$个整数，第$i$个整数表示$C_i$.

输出

输出$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$ 改为 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，然后将 $S$,改为 0，总共的代价是5x2+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$