The width of a sequence is the difference between the maximum and minimum elements in the sequence.

Given an array of integers nums, return the sum of the widths of all the non-empty subsequences of nums. Since the answer may be very large, return it modulo 109 + 7.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

&nbsp;
Example 1:

Input: nums = [2,1,3]
Output: 6
Explanation: The 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.


Example 2:

Input: nums = [2]
Output: 0


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 105
	1 &lt;= nums[i] &lt;= 105


class Solution:
    def sumSubseqWidths(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        M = 10**9+7
        res = 0
        le = 1
        re = pow(2, n-1, M)
        #by Fermat's Little Thm
        #inverse of 2 modulo M
        inv = pow(2, M-2, M)
        for num in nums:
            res = (res + num * (le - re))%M
            le = (le * 2) % M
            re = (re * inv) % M
        return res
class Solution {
    public int sumSubseqWidths(int[] nums) {
        int MOD = (int)1e9 + 7;
        Arrays.sort(nums);

        long ans = 0;
        long p = 1;
        for(int i = 0; i < nums.length; i++){
            ans = (ans + p * nums[i] - p * nums[nums.length - 1 - i]) % MOD;
            p = (p * 2) % MOD;
        }
        return (int)ans;
    }
}
class Solution {
public:
    int sumSubseqWidths(vector<int>& nums) {
        vector < long long > pow(nums.size() ); 
        pow[0] = 1;
          for(int i = 1 ; i<nums.size(); i++){ 
             pow[i] = pow[i-1] * 2 % 1000000007; 
          }
        sort(nums.begin() , nums.end()); 
       long long ans = 0 ;   
        for(int i = 0 ; i<nums.size(); i++){ 
              ans = (ans + pow[i]*nums[i]) % 1000000007; 
               ans = (ans - pow[nums.size()-i-1] * (long long)nums[i] ) % 1000000007; 
           
          } 
        return ans; 
    }
};
var sumSubseqWidths = function(nums) {
    const mod = 1000000007;
    nums.sort((a, b) => a - b), total = 0, power = 1;
    for(let i = 0; i < nums.length; i++) {
        total = (total + nums[i] * power) % mod;
        power = (power * 2) % mod;
    }

    power = 1;
    for(let i = nums.length - 1; i >= 0; i--) {
        total = (total - nums[i] * power + mod) % mod;
        power = (power * 2) % mod;
    }

    return (total + mod) % mod
};
Sum of Subsequence Widths