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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'T = int(input())\n\nM = 10 ** 9 + 7\n\nfor _ in range(T):\n N = int(input())\n\n A = list(map(int, input().split()))\n\n if N == 1:\n  print(0)\n  continue\n\n B = {}\n C = {}\n\n for i in range(N - 1):\n  u, v = input().split()\n  u = int(u) - 1\n  v = int(v) - 1\n\n  if u not in B:\n   B[u] = []\n\n  if v not in B:\n   B[v] = []\n\n  B[u].append(v)\n  B[v].append(u)\n\n total_leaves = 0\n\n for i in B:\n  if len(B[i]) == 1:\n   total_leaves += 1\n\n S = [0]\n\n visited = [False] * N\n\n parent = [-1] * N\n\n total_visits = [0] * N\n\n while len(S) > 0:\n  current = S.pop(len(S) - 1)\n\n  if visited[current]:\n   p = parent[current]\n   if p != -1:\n    total_visits[p] += total_visits[current]\n    if p not in C:\n     C[p] = {}\n    C[p][current] = total_visits[current]\n    if current not in C:\n     C[current] = {}\n    C[current][p] = total_leaves - C[p][current]\n  else:\n   S.append(current)\n   visited[current] = True\n   for i, j in enumerate(B[current]):\n    if not visited[j]:\n     parent[j] = current\n     S.append(j)\n   if len(B[current]) == 1:\n    total_visits[current] = 1\n    p = parent[current]\n    if p != -1:\n     if p not in C:\n      C[p] = {}\n     C[p][current] = 1\n\n D = {}\n for i in C:\n  sum1 = 0\n  for j in C[i]:\n   sum1 += C[i][j]\n  D[i] = sum1\n\n E = [0] * N\n for i in C:\n  sum1 = 0\n  for j in C[i]:\n   D[i] -= C[i][j]\n   sum1 += C[i][j] * D[i]\n  E[i] = sum1\n\n for i, j in enumerate(E):\n  if j == 0:\n   for k in C[i]:\n    E[i] = C[i][k]\n\n E.sort()\n E.reverse()\n A.sort()\n A.reverse()\n\n E = [x % M for x in E]\n A = [x % M for x in A]\n\n ans = 0\n for i, j in zip(E, A):\n  a = i * j\n  a %= M\n  ans += a\n  ans %= M\n\n print(ans)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14683