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).

Examples

Input

1
1000000000


Output

999999993


Input

2
5 8


Output

124


Input

5
52 67 72 25 79


Output

269312
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.Comparator;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author Silviase
 */
public class Main {

  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    Scanner in = new Scanner(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    ABC150E solver = new ABC150E();
    solver.solve(1, in, out);
    out.close();
  }

  static class ABC150E {

    public void solve(int testNumber, Scanner in, PrintWriter out) {
      int n = in.nextInt();
      ModInt res = new ModInt(0);
      ArrayList<Integer> c = new ArrayList<>();
      for (int i = 0; i < n; i++) {
        c.add(in.nextInt());
      }
      c.sort(Comparator.comparing(x -> -x));
      if (n == 1) {
        res = new ModInt(c.get(0));
      } else {
        for (int i = 0; i < n; i++) {
          res = res.add(new ModInt(i + 2).mul(new ModInt(2).pow(n - 2)).mul(new ModInt(c.get(i))));
          // out.println(res);
        }
      }
      out.println(res.mul(new ModInt(2).pow(n)));
    }

  }

  static class ModInt {

    private static int MOD = 1000000007;
    long x;

    ModInt(long l) {
      this.x = l % MOD;
    }

    ModInt add(ModInt mi) {
      return new ModInt(this.x + mi.x);
    }

    ModInt mul(ModInt mi) {
      return new ModInt(this.x * mi.x);
    }

    ModInt pow(int p) {
      ModInt res = new ModInt(1);
      ModInt tmp = this;
      while (p > 0) {
        if ((p & 1) == 1) {
          res = res.mul(tmp);
        }
        tmp = tmp.mul(tmp);
        p /= 2;
      }
      return res;
    }

    public String toString() {
      return Integer.toString((int) this.x);
    }

  }
}

