<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code> representing the strength of some heroes. The<b> power</b> of a group of heroes is defined as follows:</p>

<ul>
	<li>Let <code>i<sub>0</sub></code>, <code>i<sub>1</sub></code>, ... ,<code>i<sub>k</sub></code> be the indices of the heroes in a group. Then, the power of this group is <code>max(nums[i<sub>0</sub>], nums[i<sub>1</sub>], ... ,nums[i<sub>k</sub>])<sup>2</sup> * min(nums[i<sub>0</sub>], nums[i<sub>1</sub>], ... ,nums[i<sub>k</sub>])</code>.</li>
</ul>

<p>Return <em>the sum of the <strong>power</strong> of all <strong>non-empty</strong> groups of heroes possible.</em> Since the sum could be very large, return it <strong>modulo</strong> <code>10<sup>9 </sup>+ 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,1,4]
<strong>Output:</strong> 141
<strong>Explanation:</strong> 
1<sup>st</sup>&nbsp;group: [2] has power = 2<sup>2</sup>&nbsp;* 2 = 8.
2<sup>nd</sup>&nbsp;group: [1] has power = 1<sup>2</sup> * 1 = 1. 
3<sup>rd</sup>&nbsp;group: [4] has power = 4<sup>2</sup> * 4 = 64. 
4<sup>th</sup>&nbsp;group: [2,1] has power = 2<sup>2</sup> * 1 = 4. 
5<sup>th</sup>&nbsp;group: [2,4] has power = 4<sup>2</sup> * 2 = 32. 
6<sup>th</sup>&nbsp;group: [1,4] has power = 4<sup>2</sup> * 1 = 16. 
​​​​​​​7<sup>th</sup>&nbsp;group: [2,1,4] has power = 4<sup>2</sup>​​​​​​​ * 1 = 16. 
The sum of powers of all groups is 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141.

</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,1]
<strong>Output:</strong> 7
<strong>Explanation:</strong> A total of 7 groups are possible, and the power of each group will be 1. Therefore, the sum of the powers of all groups is 7.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

def inpu():
    return list(map(int,input().split()))
# a = int(input())

from collections import Counter, defaultdict
from typing import List

# dp = defaultdict(int)
# b = inpu()
# hu = -1
# tmp = 1
# cp = defaultdict(int)
# for i in range(len(b)):
#     dp[b[i]] = dp[b[i]-1]+1
#     if dp[b[i]] > tmp:
#         tmp = dp[b[i]]
#         hu = b[i]
#     if b[i] not in cp:
#         cp[b[i]] = i+1
# # print(cp)
# # print(dp)
# # print(hu)
# if tmp == 1:
#     print(1)
#     print(1)
#     exit(0)
# ans = []
# ct = dp[hu]+1
# while hu in dp and dp[hu] <= ct:
#     ans.append(cp[hu])
#     hu -= 1
#     ct = min(dp[hu],ct)
#     if ct == 0:
#         break

# print(len(ans))
# print(*ans[::-1])

# 
# def dfs(i,par,col):
#     t = True
#     for j in dp[i]:
#         if j == par:
#             continue
#         t = t and dfs(j,i,col)
#     if t and color[i] == col:
#         return True
#     return False


# q = int(input())
# dp = defaultdict(list)
# for i in range(q+1):
#     dp[i] = []
# for _ in range(q-1):
#     a = inpu()
#     dp[a[0]].append(a[1])
#     dp[a[1]].append(a[0])
# b = inpu()
# color = b.copy()
# color.insert(0,0)

# if len(set(b)) == 1:
#     print("YES")
#     print(1)
#     exit(0)
# for i in dp:
#     k = dp[i]
#     for j in k:
#         if color[i] != color[j]:
#             for t in k:
#                 if not(dfs(t,i,color[t])):
#                     fg = 1
#                     break
#             else:
#                 print("YES")
#                 print(i)
#                 exit(0)
#             for t in dp[j]:
#                 if not(dfs(t,j,color[t])):
#                     print("NO")
#                     exit(0)
#             print("YES")
#             print(j)
#             exit(0)





# for _ in range(int(input())):
#     a = int(input())
#     b = input()
#     k = Counter(b)
#     ans = 0
#     for i in k:
#         if i!= "?":
#             ans+=min(a,k[i])
#     print(ans)


# T = int(input().strip())

# results = []
# for _ in range(T):
#     n, k = map(int, input().strip().split())
#     a = list(map(int, input().strip().split()))
    
#     a.sort()
#     cnt = 0
#     l = a[n - 1]
#     r = a[n - 1] + k - 1
#     x = 2 * k
    
#     for i in range(n):
#         lo, hi = 0, 10**12
#         while lo <= hi:
#             mid = (lo + hi) // 2
#             z = a[i] + x * mid
#             nl = z
#             nr = z + k - 1
            
#             if nr < l:
#                 lo = mid + 1
#                 continue
#             if nl > r:
#                 hi = mid - 1
#                 continue
            
#             cnt += 1
#             l = max(l, nl)
#             r = min(r, nr)
#             break
        
#         if l > r:
#             l, r = float('inf'), float('-inf')
#             break
    
#     if l > r or cnt != n:
#         results.append("-1")
#     else:
#         results.append(str(l))

# print("\n".join(results))
MOD = int(1e9) + 7
class Solution:
    def sumOfPower(self, nums: List[int]) -> int:
        tmp = 0
        nums.sort()
        ans = 0
        for i in nums:
            k = pow(i,3,MOD)
            ans+=k
        for i in range(1,len(nums)):
            k = pow(nums[i],2,MOD)
            tmp*=2
            tmp+=nums[i-1]
            k*=tmp
            ans+=k
            ans%=MOD
        return ans
        
# a = Solution()
# print(a.sumOfPower([1,1,1]))
1598