E - Change a Little Bit /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

0, 1 からなる長さ N の異なる 2 つの数列 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 の異なる 2 つの数列の組 (S, T)2^N \times (2^N - 1) 通り考えられます。これらすべてに対する 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

0, 1 からなる長さ 1 の異なる 2 つの数列の組 (S, T) は以下の 2 通りが考えられます。

  • S = (0), T = (1): S_11 に変更することでコスト 1000000000S = T とできるため、f(S, T) = 1000000000 です。

  • S = (1), T = (0): S_10 に変更することでコスト 1000000000S = T とできるため、f(S, T) = 1000000000 です。

これらの和は 2000000000 であり、これを 10^9+7 で割った余りは 999999993 です。


入力例 2

2
5 8

出力例 2

124

0, 1 からなる長さ 2 の異なる 2 つの数列の組 (S, T)12 通り存在し、例えば以下のものが考えられます。

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

この場合、1 回目の操作で S_11 に変更し、2 回目の操作で S_20 に変更するとき、操作のコストの和は 5 \times 2 + 8 = 18 です。これより小さいコストで S = T とすることはできないので、f(S, T) = 18 です。


入力例 3

5
52 67 72 25 79

出力例 3

269312

Score : 500 points

Problem Statement

For two sequences S and T of length N consisting of 0 and 1, let us define f(S, T) as follows:

  • Consider repeating the following operation on S so that S will be equal to T. f(S, T) is the minimum possible total cost of those operations.

    • Change S_i (from 0 to 1 or vice versa). The cost of this operation is D \times C_i, where D is the number of integers j such that S_j \neq T_j (1 \leq j \leq N) just before this change.

There are 2^N \times (2^N - 1) pairs (S, T) of different sequences of length N consisting of 0 and 1. Compute the sum of f(S, T) over all of those pairs, modulo (10^9+7).

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq C_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
C_1 C_2 \cdots C_N

Output

Print the sum of f(S, T), modulo (10^9+7).


Sample Input 1

1
1000000000

Sample Output 1

999999993

There are two pairs (S, T) of different sequences of length 2 consisting of 0 and 1, as follows:

  • S = (0), T = (1): by changing S_1 to 1, we can have S = T at the cost of 1000000000, so f(S, T) = 1000000000.
  • S = (1), T = (0): by changing S_1 to 0, we can have S = T at the cost of 1000000000, so f(S, T) = 1000000000.

The sum of these is 2000000000, and we should print it modulo (10^9+7), that is, 999999993.


Sample Input 2

2
5 8

Sample Output 2

124

There are 12 pairs (S, T) of different sequences of length 3 consisting of 0 and 1, which include:

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

In this case, if we first change S_1 to 1 then change S_2 to 0, the total cost is 5 \times 2 + 8 = 18. We cannot have S = T at a smaller cost, so f(S, T) = 18.


Sample Input 3

5
52 67 72 25 79

Sample Output 3

269312