You are given a tree that consists of $n$ nodes. You should label each of its $n-1$ edges with an integer in such way that satisfies the following conditions:   each integer must be greater than $0$;  the product of all $n-1$ numbers should be equal to $k$;  the number of $1$-s among all $n-1$ integers must be minimum possible. 

Let's define $f(u,v)$ as the sum of the numbers on the simple path from node $u$ to node $v$. Also, let $\sum\limits_{i=1}^{n-1} \sum\limits_{j=i+1}^n f(i,j)$ be a distribution index of the tree.

Find the maximum possible distribution index you can get. Since answer can be too large, print it modulo $10^9 + 7$.

In this problem, since the number $k$ can be large, the result of the prime factorization of $k$ is given instead.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$) — the number of nodes in the tree.

Each of the next $n-1$ lines describes an edge: the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$; $u_i \ne v_i$) — indices of vertices connected by the $i$-th edge.

Next line contains a single integer $m$ ($1 \le m \le 6 \cdot 10^4$) — the number of prime factors of $k$.

Next line contains $m$ prime numbers $p_1, p_2, \ldots, p_m$ ($2 \le p_i < 6 \cdot 10^4$) such that $k = p_1 \cdot p_2 \cdot \ldots \cdot p_m$.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$, the sum of $m$ over all test cases doesn't exceed $6 \cdot 10^4$, and the given edges for each test cases form a tree.


-----Output-----

Print the maximum distribution index you can get. Since answer can be too large, print it modulo $10^9+7$.


-----Example-----
Input
3
4
1 2
2 3
3 4
2
2 2
4
3 4
1 3
3 2
2
3 2
7
6 1
2 3
4 6
7 3
5 1
3 6
4
7 5 13 3

Output
17
18
286



-----Note-----

 In the first test case, one of the optimal ways is on the following image:

 [Image] 

 In this case, $f(1,2)=1$, $f(1,3)=3$, $f(1,4)=5$, $f(2,3)=2$, $f(2,4)=4$, $f(3,4)=2$, so the sum of these $6$ numbers is $17$.

 In the second test case, one of the optimal ways is on the following image:

 [Image] 

 In this case, $f(1,2)=3$, $f(1,3)=1$, $f(1,4)=4$, $f(2,3)=2$, $f(2,4)=5$, $f(3,4)=3$, so the sum of these $6$ numbers is $18$.

Difficulty: interview

Starter code:

Solutions:
import sys
from collections import deque

input=sys.stdin.readline

for _ in range(int(input())):
    n=int(input())
    edge=[[] for i in range(n)]
    for i in range(n-1):
        u,v=list(map(int,input().split()))
        edge[u-1].append(v-1)
        edge[v-1].append(u-1)
    m=int(input())
    p=list(map(int,input().split()))

    size=[1 for i in range(n)]
    parent=[-1 for i in range(n)]
    res=[]
    deq=deque([(0,-1)])
    while deq:
        v,pv=deq.popleft()
        res.append(v)
        for nv in edge[v]:
            if nv!=pv:
                parent[nv]=v
                deq.append((nv,v))

    res=res[::-1]
    for v in res:
        for nv in edge[v]:
            if nv!=parent[v]:
                size[v]+=size[nv]

    coef=[]
    for v in res:
        for nv in edge[v]:
            if nv!=parent[v]:
                c=size[nv]*(n-size[nv])
                coef.append(c)
    mod=10**9+7
    #print(coef)
    #print(p)
    #print(size)
    if m<n-1:
        res=0
        coef.sort(reverse=True)
        p.sort(reverse=True)
        for i in range(m):
            res+=coef[i]*p[i]
            res%=mod
        for i in range(m,n-1):
            res+=coef[i]
            res%=mod
        print(res)
    else:
        res=0
        coef.sort()
        p.sort()
        for i in range(n-2):
            res+=coef[i]*p[i]
            res%=mod
        tmp=coef[-1]
        for i in range(n-2,m):
            tmp*=p[i]
            tmp%=mod
        res=(res+tmp)%mod
        print(res)


mod = 10**9+7
import sys
input = sys.stdin.readline
from collections import deque

class Graph(object):
	"""docstring for Graph"""
	def __init__(self,n,d): # Number of nodes and d is True if directed
		self.n = n
		self.graph = [[] for i in range(n)]
		self.parent = [-1 for i in range(n)]
		self.directed = d
		
	def addEdge(self,x,y):
		self.graph[x].append(y)
		if not self.directed:
			self.graph[y].append(x)

	def bfs(self, root): # NORMAL BFS
		queue = [root]
		queue = deque(queue)
		vis = [0]*self.n
		while len(queue)!=0:
			element = queue.popleft()
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i]==0:
					queue.append(i)
					self.parent[i] = element
					vis[i] = 1

	def dfs(self, root, ans): # Iterative DFS
		stack=[root]
		vis=[0]*self.n
		stack2=[]
		while len(stack)!=0: # INITIAL TRAVERSAL
			element = stack.pop()
			if vis[element]:
				continue
			vis[element] = 1
			stack2.append(element)
			for i in self.graph[element]:
				if vis[i]==0:
					self.parent[i] = element
					stack.append(i)

		while len(stack2)!=0: # BACKTRACING. Modify the loop according to the question
			element = stack2.pop()
			m = 0
			for i in self.graph[element]:
				if i!=self.parent[element]:
					m += ans[i]
			ans[element] = m+1
		return ans

	def shortestpath(self, source, dest): # Calculate Shortest Path between two nodes
		self.bfs(source)
		path = [dest]
		while self.parent[path[-1]]!=-1:
			path.append(parent[path[-1]])
		return path[::-1]

	def detect_cycle(self):
		indeg = [0]*self.n
		for i in range(self.n):
			for j in self.graph[i]:
				indeg[j] += 1
		q = deque()
		vis = 0
		for i in range(self.n):
			if indeg[i]==0:
				q.append(i)
		while len(q)!=0:
			e = q.popleft()
			vis += 1
			for i in self.graph[e]:
				indeg[i] -= 1
				if indeg[i]==0:
					q.append(i)
		if vis!=self.n:
			return True
		return False

	def reroot(self, root, ans):
		stack = [root]
		vis = [0]*n
		while len(stack)!=0:
			e = stack[-1]
			if vis[e]:
				stack.pop()
				# Reverse_The_Change()
				continue
			vis[e] = 1
			for i in graph[e]:
				if not vis[e]:
					stack.append(i)
			if self.parent[e]==-1:
				continue
			# Change_The_Answers()

	def maximizeSum(self):
		edges = []
		for i in range(1,n):
			edges.append(count[i]*(n-count[i]))
		edges.sort()
		# print (edges)

		ans = 0
		for i in range(n-1):
			ans += (edges[i]*a[i])%mod
			ans = ans%mod

		return (ans)



for nt in range(int(input())):
	n = int(input())
	g = Graph(n,False)
	for i in range(n-1):
		x,y = list(map(int,input().split()))
		g.addEdge(x-1,y-1)


	m = int(input())
	a = list(map(int,input().split()))
	if m<=n-1:
		a.extend([1]*(n-1-m))
		a.sort()
	else:
		a.sort()
		x = 1
		for i in range(n-2,m):
			x = (x*a[i])%mod
			x = x%mod
		a = a[0:n-2]+[x]
	# print (a)
	count = [0]*n
	count = g.dfs(0,count)
	# print (count)
	print(g.maximizeSum()) 


import sys
input = sys.stdin.readline
mod=1000000007
for f in range(int(input())):
    n=int(input())
    
    neig=[0]*n
    for i in range(n):
        neig[i]=[0]
    edges=[]
    for i in range(n-1):
        vertexa,vertexb=map(int,input().split())
        vertexa-=1
        vertexb-=1
        neig[vertexa][0]+=1
        neig[vertexb][0]+=1
        neig[vertexa].append(vertexb)
        neig[vertexb].append(vertexa)
        edges.append([vertexa,vertexb])
    tod=[]
    upn=[-1]*n
    dn=[1]*n
    for i in range(n):
        if neig[i][0]==1:
            tod.append(i)
    while len(tod)>0:
        x=tod.pop()
        neig[x][0]=0
        for foo in range(1,len(neig[x])):
            v=neig[x][foo]
            if neig[v][0]>0:
                neig[v][0]-=1
                upn[x]=v
                dn[v]+=dn[x]
                if neig[v][0]==1:
                    tod.append(v)
    m=int(input())
    p=list(map(int,input().split()))
    p.sort(reverse=True)
    facs=[1]*(n-1)
    if m<n:
        for i in range(m):
            facs[i]=p[i]
    else:
        diff=m-(n-1)
        for j in range(diff):
            facs[0]*=p[j]
            facs[0]%=mod
        for j in range(diff,m):
            facs[j-diff]*=p[j]
    wedgies=[0]*(n-1)
    for i in range(n-1):
        a,b=edges[i][0],edges[i][1]
        if upn[a]==b:
            wedgies[i]=dn[a]*(n-dn[a])
        else:
            wedgies[i]=dn[b]*(n-dn[b])
    wedgies.sort(reverse=True)
    sol=0
    for i in range(n-1):
        sol+=wedgies[i]*facs[i]
        sol%=mod
    print(sol)