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 ∑_{i=1}^{n-1} ∑_{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 ≤ t ≤ 100) — the number of test cases.

The first line of each test case contains a single integer n (2 ≤ n ≤ 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 ≤ u_i, v_i ≤ n; u_i ≠ v_i) — indices of vertices connected by the i-th edge.

Next line contains a single integer m (1 ≤ m ≤ 6 ⋅ 10^4) — the number of prime factors of k.

Next line contains m prime numbers p_1, p_2, …, p_m (2 ≤ p_i < 6 ⋅ 10^4) such that k = p_1 ⋅ p_2 ⋅ … ⋅ 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 ⋅ 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.
import sys
input = sys.stdin.readline

def getInts():
    return [int(s) for s in input().split()]

def getInt():
    return int(input())

def getStrs():
    return [s for s in input().split()]

def getStr():
    return input().strip()

def listStr():
    return list(input().strip())

import collections as col
import math,itertools

"""
For each edge, we find g = x*(N-x), where x is the number in the subtree of the child. This edge is on x*(N-x) different paths.
In order to ensure that there are minimal 1s, we assign 1 to the (N-M) edges with minimal g if M < N, otherwise there are no ones
Then for any remaining edges, we assign the lowest remaining prime factor to them
Then the product of all remaining factors is added to the edge with maximum g
"""

MOD = 10**9+7
    
from types import GeneratorType

def solve():
 
    def bootstrap(f, stack=[]):
        def wrappedfunc(*args, **kwargs):
            if stack:
                return f(*args, **kwargs)
            else:
                to = f(*args, **kwargs)
                while True:
                    if type(to) is GeneratorType:
                        stack.append(to)
                        to = next(to)
                    else:
                        stack.pop()
                        if not stack:
                            break
                        to = stack[-1].send(to)
                return to
        return wrappedfunc

    @bootstrap
    def numberOfNodes(s, e):  
        subtree[s] = 1
        for u in graph[s]:  
            if u == e:  
                continue
            yield numberOfNodes(u, s)  
            subtree[s] += subtree[u]  
        yield
    
    N = getInt()
    edges = []
    graph = col.defaultdict(set)
    for n in range(N-1):
        U, V = getInts()
        graph[U].add(V)
        graph[V].add(U)
        edges.append((min(U,V),max(U,V)))
    
    M = getInt()
    P = getInts()
    P.sort(reverse=True)
    subtree = [0]*(N+1)
    numberOfNodes(1,0)
    edge_conts = []
    for U,V in edges:
        x = min(subtree[U],subtree[V])
        edge_conts.append(((N-x)*x))
    edge_conts.sort(reverse=True)
    ans = 0
    if M < N-1:
        ans = sum(edge_conts[M:])
        edge_conts = edge_conts[:M]
    for i in range(len(edge_conts)-1):
        p = P.pop()
        e = edge_conts.pop()
        ans += e*p
        ans %= MOD
    curr = 1
    for p in P:
        curr *= p
        curr %= MOD
    ans += edge_conts[0]*curr
    ans %= MOD
    
    return ans
    
#print(solve())
for _ in range(getInt()):
    print(solve())
    
