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.util.Arrays;
import java.util.Scanner;

public class Main {

    static final long MOD = (long) (1e9 + 7);
    static int n;
    static long[] a;
    static long[] f;
    static long[] inv;
    static long[] C;
    static long[] P;
    static long[] F;

    private static long modPow(long b, long e) {
        if(e == 0) return 1;
        if(e == 1) return b;
        return modPow(b*b % MOD, e >> 1) * modPow(b, e & 1) % MOD;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        // Setup
        f = new long[n + 1];
        f[0] = 1;
        for(int i = 1; i <= n; i++) f[i] = f[i-1] * i % MOD;
        inv = new long[n + 1];
        inv[0] = 1;
        for(int i = 1; i <= n; i++) inv[i] = modPow(f[i], MOD - 2);
        C = new long[n + 1];
        for(int i = 1; i <= n; i++) C[i] = f[n] * inv[n - i] % MOD * inv[i] % MOD;
        P = new long[2 * n  + 10];
        P[0] = 1;
        for(int i = 1; i < P.length; i++) {
            P[i] = P[i-1] * 2 % MOD;
        }
        F = new long[Integer.max(n + 1, 3)];
        F[0] = 0;
        F[1] = 1;
        F[2] = 4;
        for(int i = 3; i <= n; i++) {
            F[i] = F[i-1] * (F[i-1] - F[i-2]) % MOD * modPow(F[i-2] - F[i-3], MOD - 2) % MOD;
        }
        a = new long[n + 1];
        for(int i = 1; i <= n; i++) a[i] = sc.nextInt();
        Arrays.sort(a);
        for(int i = 1; i <= n / 2; i++) {
            long tmp = a[i];
            a[i] = a[n - i + 1];
            a[n - i + 1] = tmp;
        }


        long ans = 0;
        for(int i = 1; i <= n; i++) {
            ans += (F[i-1] + P[i-1]) * a[i] % MOD * P[n - i] % MOD;
            ans %= MOD;
        }

        ans *= P[n];
        ans %= MOD;
        if(ans < 0) ans += MOD;
        System.out.println(ans);
    }
}
