Given an array of integers A, consider all non-empty subsequences of A.
For any sequence S, let the width of S be the difference between the maximum and minimum element of S.
Return the sum of the widths of all subsequences of A. 
As the answer may be very large, return the answer modulo 10^9 + 7.

 
Example 1:
Input: [2,1,3]
Output: 6
Explanation:
Subsequences are [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3].
The corresponding widths are 0, 0, 0, 1, 1, 2, 2.
The sum of these widths is 6.

 
Note:

1 <= A.length <= 20000
1 <= A[i] <= 20000

Difficulty: interview

Starter code:

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        

Solutions:
class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        ret, mod, p = 0, 10 ** 9 + 7, 1
        for i in range(len(A)): 
            ret += (A[i] - A[len(A) - i - 1]) * p % mod
            p = (p << 1) % mod
        return ret % mod

mod_ = 10**9 + 7

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        n = len(A)
        p_2 = [1]
        for i in range(1,n+2):
            p_2.append((p_2[-1]*2)%mod_)
        l = [0]
        for i in range(1,n):
            l.append( (2*l[-1] + (A[i]-A[i-1]) * (p_2[i]-1) ) % mod_ )
        sol = 0
        for elem in l:
            sol = (sol + elem) % mod_
        return sol

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        '''
        1 2 3
            x
        '''
        ret = 0
        for i, n in enumerate(sorted(A)):
            ret += n * pow(2, i)
            ret -= n * pow(2, len(A) - i - 1)
            ret %= 10**9 + 7
        
        return ret

from bisect import bisect_left, bisect_right

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        n = len(A)
        ret = 0
        
        # F[i] number of subsequences accept A[i] as minimun
        # G[i] number of subsequences accept A[i] as maximum
        # result = (-F[i] + G[i]) * A[i]        
        
        A.sort()   
        ret = 0
        f = {}
        
        for i, x in enumerate(A):
            if x not in f:
                f[x] = [i, i]
            else:
                f[x][1] = i

        ret = 0
        
        for x in f:
            l, r = f[x]
            sl = l
            sr = n-r-1
            se = r-l+1
            ret += (2**sl-1) * (2**se-1) * x
            ret -= (2**sr-1) * (2**se-1) * x
        
        return ret % (10 ** 9 + 7)
        

            
            
    
            
            
            
            
            


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        MOD = 10**9 + 7
        N = len(A)
        A.sort()

        pow2 = [1]
        for i in range(1, N):
            pow2.append(pow2[-1] * 2 % MOD)

        ans = 0
        for i, x in enumerate(A):
            ans = (ans + (pow2[i] - pow2[N-1-i]) * x) % MOD
        return ans
           


class Solution:
    
    BASE = 10 ** 9 + 7
    
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        total_cnt = 0
        total_prod = 0
        ans = 0
        for num in A:
            ans = (ans + total_cnt * num - total_prod) % self.BASE
            total_cnt = (2 * total_cnt + 1) % self.BASE
            total_prod = (2 * total_prod + num) % self.BASE
        return ans

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        
        # # N^2log(N) time over limit
        # aa = sorted(A)
        # n = len(A)
        # res = 0
        # # print(aa)
        # for i in range(n):
        #     for j in range(i+1,n):
        #         res = (res+2**(j-i-1)*(aa[j]-aa[i]))%(10**9+7)
        #         # print(i,j,aa[i],aa[j],res)
        # return res
        
        # above simplified (simple math), NlogN time
        aa = sorted(A)
        n = len(A)
        res = 0
        # print(aa)
        md = 10**9 + 7
        p2 = [1]*n
        for i in range(1,n):
            p2[i] = (p2[i-1]*2) % md
        for i in range(n):
            res = (res+aa[i]*(p2[i]-p2[n-i-1])) % md
        return res


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        N = len(A)
        if N==1: return 0
        MOD = 10**9 + 7
        A.sort()
        pow2 = [1]
        widths = 0
        for i in range(1, N):
            pow2.append(pow2[-1] * 2 % MOD)
            
        for i in range(N):
            widths = (widths + (pow2[i] - pow2[N-1-i]) * A[i]) % MOD
            
        return widths

from collections import deque

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        n = len(A)
        
        MOD = 10 ** 9 + 7
        
        pows = [1] * n
        for i in range(1, n):
            pows[i] = (pows[i-1] * 2) % MOD
        
        A.sort()
        ans = 0
        
        for i, v in enumerate(A):
            ans += pows[i] * v - pows[n-1-i] * v
            ans %= MOD
            
        return ans  % MOD
        
        
        
        
            


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        result = 0
        for i in range(len(A)):
            result *= 2
            result -= A[i]
            result += A[~i]
        return result % (10 ** 9 + 7)

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        if len(A)==1:   return 0
        if len(A)==0:   return 0
        ans, prev, n, mod = A[1]-A[0], A[1]-A[0], len(A), 1e9+7
        twoPow, temp=[1], 2
        for i in range(1,n):
            twoPow.append(temp+twoPow[-1])
            temp = (temp*2)%mod   
        for i in range(2, len(A)):
            diff = A[i]-A[i-1]
            prev = ((2*(prev + (diff*twoPow[i-2])%mod))%mod + diff)%mod
            ans = (ans + prev)%mod
        return int(ans)

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        res = 0
        n = len(A)
        M = 10**9 + 7
        c = 1
        A.sort()
        
        for i in range(n):
            res = (res + A[i] *c - A[n - i - 1] * c )%M
            #print(res)
            c = (c<<1)%M
        return res


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        # Mathematical
        # Sum_{j > i} (2^(j - i - 1)) x (A_j - A_i) = Sum_{i = 0}^{n - 1} (2^i - 2^(N - i - 1)) x A_i
        # Time  complexity: O(NlogN), where N is the length of A.
        # Space complexity: O(N)
        MOD = 10**9 + 7
        N = len(A)
        A.sort()

        pow2 = [1]
        for i in range(1, N):
            pow2.append(pow2[-1] * 2 % MOD)

        ans = 0
        for i, x in enumerate(A):
            ans = (ans + (pow2[i] - pow2[N - i - 1]) * x) % MOD 

        return ans



class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        size = len(A)
        mod = 10 ** 9 + 7
        pow_mod = [1] * size
        for i in range(1, size): 
            pow_mod[i] = (pow_mod[i-1] * 2) % mod
        
        A.sort()
        ans = 0
        for i in range(size): 
            ans += (A[i] * ((pow_mod[i] - pow_mod[size-1-i]) % mod)) % mod
            ans %= mod
        return ans

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        res = 0
        n = len(A)
        for i in range(n):
            res += A[i] * 1<<i % 1000000007
            res -= A[i] * 1<<(n-i-1)
        return res % 1000000007

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        ret = 0
        for i in range(len(A)):
            # how many subseq contain me as the min/max?
            ret -= A[i]<<(len(A)-i-1)
            ret += A[i]<<i
        return ret%(10**9+7)

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        MOD = 10 ** 9 + 7
        A.sort()
        result = 0
        prev = 0
        for i in range(1, len(A)):
            d = A[i] - A[i - 1]
            prev = (2 * prev + d * (pow(2, i, MOD) - 1)) % MOD
            result = (result + prev) % MOD
        return result

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        res = 0
        A.sort()
        for i in range(0, len(A)):
            res += A[i] * ((1<<i) - (1<<(len(A)-i-1)))
        return res % (10**9+7)
            


class Solution:
    def sumSubseqWidths(self, A):
        return sum(((1 << i) - (1 << len(A) - i - 1)) * a for i, a in enumerate(sorted(A))) % (10**9 + 7)

class Solution:
    # def sumSubseqWidths(self, A: List[int]) -> int:
    #     A = sorted(A)
    #     total, cur, cnt = 0, 0, 0
    #     MOD = 10**9 + 7
    #     for i in range(1,len(A)):
    #         cnt *= 2
    #         cnt += 1
    #         cur *= 2
    #         cur += (A[i]-A[i-1])*cnt
    #         cur %= MOD
    #         total += cur
    #         total %= MOD
    #         # print(cur,cnt)
    #     return total

    
    def sumSubseqWidths(self, A):
        return sum(((1 << i) - (1 << len(A) - i - 1)) * a for i, a in enumerate(sorted(A))) % (10**9 + 7)

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        MOD = 10 ** 9 + 7
        A.sort()
        result = 0
        prev = 0
        powmod = 1
        for i in range(1, len(A)):
            d = A[i] - A[i - 1]
            powmod = (powmod * 2) % MOD
            prev = (2 * prev + d * (powmod - 1)) % MOD
            result = (result + prev) % MOD
        return result

class Solution:
     def sumSubseqWidths(self, A):
        return sum(((1 << i) - (1 << len(A) - i - 1)) * a for i, a in enumerate(sorted(A))) % (10**9 + 7)


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        B = sorted(A)
        res = 0
        mod = 10**9 + 7
        for i in range(len(B)):
            res += B[i] * ((1 << i) - (1 << (len(B) - i - 1)))
        return res % mod

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        if not A: return 0
        ans = 0
        A.sort()
        for i, n in enumerate(A):
            ans += ((1<<i)-(1<<(len(A)-i-1)))*n
            
        return ans%(10**9+7)


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        return sum((1 << i) * num - (1 << len(A) - i - 1) * num for i, num in enumerate(sorted(A))) % (10**9 + 7)


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        mod = 10 ** 9 + 7
        A.sort()
        n = len(A)
        return sum(a * ((1 << i) - (1 << n - i - 1)) for i, a in enumerate(A)) % mod
    
        # for i, a in enumerate(A):
        #     ans += a * ((1 << i) - (1 << n - i - 1)) % mod
        # return ans % mod


class Solution:

    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        #to i, there are 2^(i)  subsequence with max A[i]
        #there are 2^(n-i-1) subseq with min A[i]
    
        ans = 0
        '''
        for i in range(len(A)):
            for j in range(i,len(A)):
                if i == j:continue
                if A[i] == A[j]: continue
                ans +=(1<< ( j-i-1))*(A[j]-A[i])
        '''
        n = len(A)
        for i, k in enumerate(A):
            #print(i,k,ans)
            
            
            ans += ((1 << (i)))* k
            
            ans -= ((1 << (n-i-1)))*k
            #ans += k*(pow(2,i)- pow(2, n-i-1))
        return ans%(10**9+7)
        
        
        


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        LIM = 10 ** 9 + 7
        res = 0
        powTable = [1]
        for _ in range(len(A)):
            powTable.append((2 * powTable[-1]) % LIM)
        for i, val in enumerate(A):
            res = (res + val * powTable[i] - val * powTable[len(A) - i - 1]) % LIM
        return res

class Solution:
    BASE = 10 ** 9 + 7
    
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        total_cnt = 0
        total_prod = 0
        ans = 0
        for num in A:
            ans = (ans + total_cnt * num - total_prod) % self.BASE
            total_cnt = (2 * total_cnt + 1) % self.BASE
            total_prod = (2 * total_prod + num) % self.BASE
        return ans


class Solution:
    def sumSubseqWidths(self, A):
        MOD = 10**9 + 7
        N = len(A)
        A.sort()

        pow2 = [1]
        for i in range(1, N):
            pow2.append(pow2[-1] * 2 % MOD)

        ans = 0
        for i, x in enumerate(A):
            ans = (ans + (pow2[i] - pow2[N-1-i]) * x) % MOD
        return ans

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        total = 0
        MOD = 10 ** 9 + 7
        powerSum = 2**0
        counter = 2
        currSum = A[0]
        for i in range(1, len(A)):
            total += (powerSum * A[i]) - currSum
            currSum *= 2
            currSum += A[i]
            powerSum += counter
            counter *= 2
           
       
        return total % MOD

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
            A.sort()
            S = 0
            B = [1]*len(A)
            for i in range(1,len(B)):
                B[i] = 2*B[i-1]
            for i in range(len(A)):
                S += (B[i]-B[-1-i])*A[i]
            return S%((10**9)+7)


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        total = 0
        
        powerSum = 2**0
        counter = 2
        currSum = A[0]
        for i in range(1, len(A)):
            total += (powerSum * A[i]) - currSum
            currSum *= 2
            currSum += A[i]
            powerSum += counter
            counter *= 2
       
        return total % (10 ** 9 + 7)  

class Solution:
    def sumSubseqWidths(self, a: List[int]) -> int:
        a.sort()
        print(a)
        count=0
        n=1
        c=a[0]
        for m,i in enumerate(a[1:]):
            n*=2
            count+=(n-1)*i-c
            c=c*2+i
        return count%(pow(10,9)+7)

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        l=len(A)
        p=[1]
        ans=0
        for i in range(1,l):
            p.append(p[-1]*2)
        for i,j in enumerate(A):
            ans+=(p[i]-p[l-i-1])*j
        return ans%( 10**9 + 7)
        
        
        
        


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        
        n = len(A)
        
        total = 0
        
        for i in range(n):
            a = A[i]

            left = i # how many elements on the left
            right = n - i - 1 # how many elements on the right
            # number of subsequences with A[i] as max is (2 ** left)
            total += ((1 << left) - 1) * a  # minus 1 so subsequence with only A[i] is not counted
            total -= ((1 << right) - 1) * a
            
        return total % (10 ** 9 + 7)

class Solution:
    def sumSubseqWidths(self, nums):
        res = 0
        for i, num in enumerate(sorted(nums)):
            res += ((1 << i) - (1 << len(nums) - i - 1)) * num

        return res % 1000000007

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A = sorted(A)
        r = 0
        m = 10 ** 9 + 7
        for i in range(len(A)-1):
            # print(r)
            # print(A[i+1] - A[i], len(A)-i)
            r += (A[i+1] - A[i]) * ((1 << (len(A))) - (1 << (i+1)) - (1 << (len(A)-i-1)) + 1)
        r %= m
        return r

class Solution(object):
    def sumSubseqWidths(self, A):
        MOD = 10**9 + 7
        N = len(A)
        A.sort()

        pow2 = [1]
        for i in range(1, N+1):
            pow2.append(pow2[-1] * 2 % MOD)

        ans = 0
        for i, x in enumerate(A):
            ans = (ans + (pow2[i] - pow2[N-1-i]) * x) % MOD
        return ans

from bisect import bisect_left, bisect_right

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        n = len(A)
        ret = 0
        
        # F[i] number of subsequences accept A[i] as minimun
        # G[i] number of subsequences accept A[i] as maximum
        # result = (-F[i] + G[i]) * A[i]        
        
        
        A.sort()   
        MOD = 10 ** 9 + 7
        
        @lru_cache
        def bimod(n):
            if n == 0:
                return 1
            di = bimod(n // 2)
            if n % 2 == 0:
                return di * di % MOD
            return di * di * 2 % MOD
        
        @lru_cache
        def nonempty(n):
            return bimod(n) - 1
        
        i = 0
        while i < n:
            j = i
            while j < n and A[j] == A[i]:
                j+=1
            se = j - i
            sl = i
            sr = n-j
            
            # ret = (ret + (2**sl-1) * (2**se-1) * A[i] % MOD) % MOD
            # ret = (ret - (2**sr-1) * (2**se-1) * A[i] % MOD) % MOD
            ret = (ret + A[i] * nonempty(se) * (nonempty(sl) - nonempty(sr)) % MOD) % MOD
            i = j
        
        return ret % MOD
        

            
            
    
            
            
            
            
            


from bisect import bisect_left, bisect_right

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        n = len(A)
        ret = 0
        
        # F[i] number of subsequences accept A[i] as minimun
        # G[i] number of subsequences accept A[i] as maximum
        # result = (-F[i] + G[i]) * A[i]        
        
        
        A.sort()   
        MOD = 10 ** 9 + 7
        
        @lru_cache
        def bimod(n):
            if n == 0:
                return 1
            di = bimod(n // 2)
            if n % 2 == 0:
                return di * di % MOD
            return di * di * 2 % MOD
        
        @lru_cache
        def nonempty(n):
            return bimod(n) - 1
        
        i = 0
        while i < n:
            j = i
            while j < n and A[j] == A[i]:
                j+=1
            se = j - i
            sl = i
            sr = n-j

            ret = (ret + A[i] * nonempty(se) * (nonempty(sl) - nonempty(sr)) % MOD) % MOD
            i = j
        
        return ret
        

            
            
    
            
            
            
            
            


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A = sorted(A)
        total, cur, cnt = 0, 0, 0
        MOD = 10**9 + 7
        for i in range(1,len(A)):
            cnt *= 2
            cnt += 1
            cur *= 2
            cur += (A[i]-A[i-1])*cnt
            cur %= MOD
            total += cur
            total %= MOD
            # print(cur,cnt)
        return total


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        
        A = sorted(A)
        res = 0
        MOD = 10**9+7
        c = 1
        for i in range(len(A)):
            res = (res + A[i]*c%MOD)%MOD
            c <<= 1
            c %= MOD
        c = 1
        for i in range(len(A)-1, -1, -1):
            res = (res - A[i]*c%MOD)%MOD
            c <<= 1
            c %= MOD
        return (res+MOD)%MOD
            
            
        


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        return sum(((1 << i) - (1 << (len(A)-i-1))) * a for i, a in enumerate(sorted(A))) % (10**9 + 7)

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        POW2 = [1 << i for i in range(len(A))]
        return sum((POW2[i] - POW2[len(A) - 1 - i]) * n for i, n in enumerate(sorted(A))) % (10 ** 9 + 7)


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        MOD = 10 ** 9 + 7
        POW2 = [(1 << i) % MOD for i in range(len(A))]
        return sum((POW2[i] - POW2[len(A) - 1 - i]) * n for i, n in enumerate(sorted(A))) % (10 ** 9 + 7)


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        return sum(((1 << i) - (1 << (len(A) - 1 - i))) * n for i, n in enumerate(sorted(A))) % (10 ** 9 + 7)


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        mod = 10**9+7
        n = len(A)
        A.sort()
        B = [A[i]-A[n-i-1] for i in range(n)]
        ans = 0
        for i, v in enumerate(B):
            ans = (ans + (v << i)) % mod
        return ans      

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        MOD = 10**9 + 7
        N = len(A)
        A.sort()
        
        pow2 = [1]
        for i in range(1, N):
            pow2.append(pow2[-1] * 2 % MOD)
        
        ans = 0
        for i, x in enumerate(A):
            ans = (ans + (pow2[i] - pow2[N - 1 -i]) * x) % MOD
        
        return ans

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        total = 0
        MOD = 10 ** 9 + 7
        powerSum = 2**0
        counter = 2
   
        currSum = A[0]
        for i in range(1, len(A)):
            total += (powerSum * A[i]) - currSum
            currSum *= 2
            currSum += A[i]
            powerSum += counter
            counter *= 2
           
        return total % MOD

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        total = 0
        MOD = 10 ** 9 + 7
        powerSum = 2**0
        counter = 2
        currSum = A[0]
        for i in range(1, len(A)):
            total += (powerSum * A[i]) - currSum
            currSum *= 2
            currSum += A[i]
            powerSum += counter
            counter *= 2
            total %= MOD
       
        return total

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        mod = 10 ** 9 + 7
        f, g = 0, 0
        ans = 0
        for i in range(1, len(A)):
            g = (2 * g + A[i - 1]) % mod
            f = (A[i] * ((1 << i) - 1) - g) % mod
            ans = (ans + f) % mod
        return ans

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        total = 0
        MOD = 10 ** 9 + 7
        powerSum = 2**0
        counter = 2
   
        currSum = A[0]
        for i in range(1, len(A)):
            total += (powerSum * A[i]) - currSum
            currSum *= 2
            currSum += A[i]
            powerSum += counter
            counter *= 2
            total %= MOD
            powerSum %= MOD
            currSum %= MOD
           
        return total % MOD

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        res = 0
        mod = 10**9+7
        N = len(A)
        for i in range(len(A)):
            res += ((1<<i)-(1<<N-i-1))*A[i]%mod

        return res%mod

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        N = len(A)
        A = sorted(A)
        MODS = 10 ** 9 + 7
        pow2, res = [1], 0
        for ii in range(1, N):
            pow2.append(2 * pow2[-1] % MODS)
        for ii, jj in enumerate(A):
            res = (res + (pow2[ii] - pow2[N - ii - 1]) * jj) % MODS
        return res


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        res = 0
        A.sort()
        for i in range(0, len(A)):
            res += A[i] * ((1<<i) - (1<<(len(A)-i-1))) % (10**9+7)
        return res % (10**9+7)
            


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        mod = 10**9+7
        n = len(A)
        A.sort()
        ans = 0
        for i, v in enumerate(A):
            ans = (ans + (v << i) - (v << (n-1-i))) % mod
        return ans        

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        mod = 10**9 + 7
        A.sort()
        n = len(A)
        ans = 0
        def exp(n):
            res = 1
            x = 2
            while n:
                if n&1:
                    res = (res*x)%mod
                n = n>>1
                x = (x*x)%mod
            
            return res
    
        for i in range(n):
            ans = (ans + exp(i)*A[i] - exp(n - i - 1)*A[i] + mod) % mod
        
        return ans

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        if not A: return 0
        n=len(A)
        A.sort()
        ans = 0
        for i in range(n):
            ans += A[i]*(1<<i)
            ans -= A[i]*(1<<(n-i-1))
            ans %= (10**9+7)
        return ans
            


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        MOD = 10**9 + 7
        N = len(A)
        A.sort()

        ans = 0
        for i, x in enumerate(A):
            ans = (ans + ((1<<i) - (1<<(N-1-i))) * x) % MOD
        return ans        

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A = sorted(A)
        r = 0
        m = 10 ** 9 + 7
        for i in range(len(A)-1):
            # print(r)
            # print(A[i+1] - A[i], len(A)-i)
            r += (A[i+1] - A[i]) * ((1 << (len(A))) - (1 << (i+1)) - (1 << (len(A)-i-1)) + 1)
            r %= m
        return r

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        total = 0
        MOD = 10 ** 9 + 7
        powerSum = 2**0
        counter = 2
   
        currSum = A[0]
        for i in range(1, len(A)):
            total += ((powerSum * A[i]) - currSum) % MOD
            currSum *= 2
            currSum += A[i]
            powerSum += counter
            counter *= 2
            powerSum %= MOD
            currSum %= MOD
           
        return total % MOD

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        mod = 10**9 + 7
        n = len(A)
        if n == 1:
            return 0
        
        pow = [1]
        for i in range(1, n):
            pow.append(pow[-1]*2%mod)
        
        A = sorted(A)
        s = 0
        for i, elem in enumerate(A):
            n_max, n_min = i, n-i-1
            N1 = pow[i]
            N2 = pow[n-i-1]
            s += ((elem*(N1-N2)) %  (10**9 + 7) )
            s = s % (10**9 + 7)
        return s

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        '''
        1 2 3
            x
        '''
        ret = 0
        mod = 10**9 + 7
        for i, n in enumerate(sorted(A)):
            ret = (ret + n * (1 << i)) % mod
            ret  = (ret - n * (1 << (len(A) - i - 1))) % mod
        
        return ret

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        res = 0
        A.sort()
        for i in range(0, len(A)):
            res += A[i] * ((1<<i) - 2**(len(A)-i-1))
        return res % (10**9+7)
            


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        
        MOD = 10**9+7
        
        A = sorted(A)
        if len(A) == 1:
            return 0
        
        lastaddon = 0
        lastv = 0
        for i in range(1, len(A)):
            lastaddon = 2*lastaddon + (2**i-1)*(A[i]-A[i-1])
            lastv += lastaddon
        
        return lastv%MOD

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        n = len(A)
        widthsum = 0
        mod = 10**9 + 7
        
        A.sort()
        
        p = s = 0
        pre, suf = [], []
        for i in range(n):
            p += A[i]
            s += A[-i-1]
            pre.append(p)
            suf.append(s)
            
        for l in range(n):
            widthsum += 2**(l)*(suf[l]-pre[l])
            widthsum %= mod
            
        return widthsum


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        N = len(A)
        return sum(num * (2 ** i - 2 ** (N - i - 1)) for i, num in enumerate(A)) % (10 ** 9 + 7)

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        
        res = 0
        
        #the order does not matter with subsequeces so first sort the array
        A.sort()
        
        for i in range(len(A)):
            #then at position i, we know that there are i smaller numbers and 2^i different subsequences where i will be the maximum, so we add 2^i times A[i]
            res += (2**i) * A[i]
            #Also, A[i] will be less than len(A) - i - 1 numbers or (2^len(A)-1-i) different combinations, so subtract that
            res -= (2**(len(A) - 1 - i)) * A[i]
            
        
        return res % ((10**9) + 7)

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        res = 0
        A.sort()
        for i in range(0, len(A)):
            res += A[i] * (2**i - 2**(len(A)-i-1))
        return res % (10**9+7)
            


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        #1.Sort the list. Then for each element, it's the maximum of a subsequence if and only if it's on the rightmost side; on the other hand, if it's the minimum then it's on the leftmost side.  
        #2.For any element A[i], suppose there are left elements on its left side and right elements on its right side. Then in 2^(left) subsequences this element appeared as the maximum element and in 2^(right) subsequences it appeares as the minimum element. So the contribution of this element to the final result would be: (2^(left)-2^(right))*A[i] = [2^i-2^(n-i-1)]*A[i]
        Mod = (1e9)+7
        n = len(A)
        #twoPower = [1]*n
        #for i in range(1, n):
         #   twoPower[i] = (twoPower[i-1]*2)% Mod
        
        twoPower = [1]
        while len(twoPower) < n:
            twoPower.append((twoPower[len(twoPower)-1]*2)% Mod)
            
        
        A.sort()
        ans = 0
        for i, a in enumerate(A):
            left = i
            right = n-i-1
            ans = (ans + (twoPower[left]-twoPower[right])*a) % Mod
            
        return int((ans+ Mod) % Mod)
        
        


class Solution:
    def sumSubseqWidths(self, A: List[int], recursed=False) -> int:
        return sum(
            x * (2 ** i - 2 ** (len(A) - i - 1)) for i, x in enumerate(sorted(A))
        ) % (int(1e9) + 7)


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A = sorted(A)
        length = len(A)
        _sum = 0
        for i in range(length):
            _sum += A[i] * 2**i
        
        for i in range(length):
            _sum -= A[i] * 2**(length-i-1)
            
        return _sum % (10**9 + 7)

class Solution:
    def sumSubseqWidths(self, A: List[int], recursed=False) -> int:
        A.sort()
        return sum(
            x * (2 ** i - 2 ** (len(A) - i - 1)) for i, x in enumerate((A))
        ) % (int(1e9) + 7)


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A = sorted(A)
        length = len(A)
        _sum = 0
        for i in range(length):
            _sum += A[i] * 2**i - A[i] * 2**(length-i-1)
        
        
        return _sum % (10**9 + 7)

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        B = sorted(A)
        res = 0
        mod = pow(10, 9) + 7
        for i in range(len(B)):
            res += B[i] * (pow(2, i) - pow(2, len(B) - i - 1))
        return res % mod

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        
        n = len(A)
        
        total = 0
        
        for i, a in enumerate(A):
            left = i # how many elements on the left
            right = n - i - 1 # how many elements on the right
            # number of subsequences with A[i] as max is (2 ** left)
            total += (2 ** left - 1) * a  # minus 1 so subsequence with only A[i] is not counted
            total -= (2 ** right - 1) * a
            
        return total % (10 ** 9 + 7)

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        res = 0
        mod = 10**9+7
        N = len(A)
        for i in range(len(A)):
            res = (res+A[i]*2**i-A[i]*(2**(N-i-1)))%mod

        return res

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        c=0
        n=len(A)
        for i in range(n):
            c=(((2**i)-(2**(n-i-1)))*A[i])+c
            c=c%(10**9+7)
        return c


class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        res = 0
        n = len(A)
        for i in range(n):
            res += A[i] * 2**i % 1000000007
            res -= A[i] * 2**(n-i-1)
        return res % 1000000007

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        total = 0
        const = 10**9+7
        for i in range(len(A)):
            total += 2**(i)*A[i]-2**(len(A)-i-1)*A[i]
            total = total % const
        return total