You are given a tree with $N$ vertices (numbered $1$ through $N$) and a sequence of integers $A_1, A_2, \ldots, A_N$. You may choose an arbitrary permutation $p_1, p_2, \ldots, p_N$ of the integers $1$ through $N$. Then, for each vertex $i$, you should assign the value $A_{p_i}$ to this vertex.
The profit of a path between two vertices $u$ and $v$ is the sum of the values assigned to the vertices on that path (including $u$ and $v$).
Let's consider only (undirected) paths that start at a leaf and end at a different leaf. Calculate the maximum possible value of the sum of profits of all such paths. Since this value could be very large, compute it modulo $10^9 + 7$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.
- Each of the following $N−1$ lines contains two space-separated integers $u$ and $v$ denoting that vertices $u$ and $v$ are connected by an edge.

-----Output-----
For each test case, print a single line containing one integer — the maximum sum of profits, modulo $10^9 + 7$.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le N \le 300,000$
- $1 \le A_i \le 10^9$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $5 \cdot 10^5$

-----Example Input-----
2
4
1 2 3 4
1 2
2 3
2 4
5
1 2 3 4 5
1 2
2 3
3 4
4 5

-----Example Output-----
24
15

-----Explanation-----
Example case 1: $(1, 4, 2, 3)$ is one of the possible permutations that give the optimal answer. Then, the profits of paths between pairs of vertices $(1, 3)$, $(1, 4)$ and $(3, 4)$ are $7$, $8$ and $9$ respectively.
Example case 2: Here, any permutation could be chosen.

Difficulty: interview

Starter code:

Solutions:
T = int(input())

M = 10 ** 9 + 7

for _ in range(T):
 N = int(input())

 A = list(map(int, input().split()))

 if N == 1:
  print(0)
  continue

 B = {}
 C = {}

 for i in range(N - 1):
  u, v = input().split()
  u = int(u) - 1
  v = int(v) - 1

  if u not in B:
   B[u] = []

  if v not in B:
   B[v] = []

  B[u].append(v)
  B[v].append(u)

 total_leaves = 0

 for i in B:
  if len(B[i]) == 1:
   total_leaves += 1

 S = [0]

 visited = [False] * N

 parent = [-1] * N

 total_visits = [0] * N

 while len(S) > 0:
  current = S.pop(len(S) - 1)

  if visited[current]:
   p = parent[current]
   if p != -1:
    total_visits[p] += total_visits[current]
    if p not in C:
     C[p] = {}
    C[p][current] = total_visits[current]
    if current not in C:
     C[current] = {}
    C[current][p] = total_leaves - C[p][current]
  else:
   S.append(current)
   visited[current] = True
   for i, j in enumerate(B[current]):
    if not visited[j]:
     parent[j] = current
     S.append(j)
   if len(B[current]) == 1:
    total_visits[current] = 1
    p = parent[current]
    if p != -1:
     if p not in C:
      C[p] = {}
     C[p][current] = 1

 D = {}
 for i in C:
  sum1 = 0
  for j in C[i]:
   sum1 += C[i][j]
  D[i] = sum1

 E = [0] * N
 for i in C:
  sum1 = 0
  for j in C[i]:
   D[i] -= C[i][j]
   sum1 += C[i][j] * D[i]
  E[i] = sum1

 for i, j in enumerate(E):
  if j == 0:
   for k in C[i]:
    E[i] = C[i][k]

 E.sort()
 E.reverse()
 A.sort()
 A.reverse()

 E = [x % M for x in E]
 A = [x % M for x in A]

 ans = 0
 for i, j in zip(E, A):
  a = i * j
  a %= M
  ans += a
  ans %= M

 print(ans)