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
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush,heappop,heapify
mod = int(1e9)+7

 
ip = lambda : int(stdin.readline())
inp = lambda: map(int,stdin.readline().split())
ips = lambda: stdin.readline().rstrip()

# DEFAULT-DICT as DD
def addEdge(a,b):
    graph[a].append(b)
    graph[b].append(a)
def Bfs(src):
    q = deque([])
    q.append(src)
    visited[src] = True
    dist[src] = 0
    while(q):
        node = q.popleft()
        for neighbour in graph[node]:
            if(not visited[neighbour]):
                q.append(neighbour)
                visited[neighbour]= True
                dist[neighbour] = dist[node]+1
                parent[neighbour] = node
                level[dist[neighbour]].append(neighbour)
def Bfs2(src):
    global total
    q = deque([])
    q.append(src)
    visited[src] = True
    while(q):
        node = q.popleft()
        for neighbour in graph[node]:
            if(not visited[neighbour]):
                q.append(neighbour)
                visited[neighbour]= True
                left = ct[neighbour]
                right = total-left
                times = left*right
                a,b = node,neighbour
                if a>b:
                    a,b = b,a
                dic[(a,b)] = times
                
                
t = ip()
for _ in range(t):
    n = ip()
    total = n
    graph = [[] for i in range(n)]
    dist = [0]*n
    parent = [-1]*n
    visited = [False]*n
    ct = [0]*n
    dic = {}
    for i in range(n-1):
        a,b = inp()
        a,b = a-1,b-1
        addEdge(a,b)
        if a>b:
            a,b = b,a
        dic[(a,b)] = 0
    m = ip()
    prime = list(inp())
    level = dd(list)
    Bfs(0)
    ch = sorted(list(level.keys()),reverse = True)
    visited = [False]*n 
    ct[0] += 1
    for i in ch:
        for j in level[i]:
            ct[j] += 1
            par = parent[j]
            ct[par] += ct[j]
    Bfs2(0)
    prime.sort()
    if len(prime)<=n-1:
        prime = [1]*(n-1-len(prime))+prime
    else:
        ct = len(prime)
        while ct != n-1:
            val = prime.pop()
            prime[-1] = (prime[-1]*val)%mod
            ct -= 1
    temp = sorted(list(dic.values()))
    ans = 0
    for i in range(n-1):
        ans += ((temp[i]%mod)*(prime[i]%mod))%mod
        ans %= mod
    print(ans)
    
    
    
    
    
        
    
    
        
    
        
        
            
            
    
    
            
    
        
             
    
                    
            
            
                        
            
            
            
