A7531. [ABC150E] Change a Little Bit

对于两个长度为 $n$ 的 $\texttt{01}$ 序列 $S,T$ ，我们定义 $f(S,T)$ 为通过以下操作将 $S$ 修改为 $T$ 的最小代价和: 选择一个 $S$ 中的二进制位 $S_{i}$ ，然后改变 $S_{i}$ 的 $\texttt{01}$ 状态，代价为 $D \times C_{i}$，其中 $D$ 是此次操作前满足 $S_{j}\ne T_{j}$ 的整数 $j$ 的数量，$C_{i}$ 是一个给定的序列中的一个值。

求当 $S$ 取 $2^n$ 种不同的状态，$T$ 取 $2^n$ 种不同的状态时，$f(S,T)$ 的和对 $1000000007$ 取模的结果。

第一行一个整数 $n$

第二行 $n$ 个整数 $C_{i}$

一行一个整数，表示答案

$1 \le n \le 200000 , 1 \le C_{i} \le 10^9$