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.
//note: 0<=|int|<=2 * 10^9
//note: 0<=|long|<= 9 * 10^18
//note: 20! max w/ long
//note: 91st fibonacci # highest calculable w/long
//note: 0 <= |double| <= 1.8 * 10^308
//note: 170! max w/long;
import java.io.*;
import java.util.*;
import java.math.BigInteger;
    
public class CP{
    private static int MAX = Integer.MAX_VALUE;
    private static int MIN = Integer.MIN_VALUE;
    private static List<Integer>[] adj;
    public static void main(String[] args) throws IOException{
        FastScanner sc = new FastScanner();
        long MOD = (long) (1e9 +7);
        out = new PrintWriter(new BufferedOutputStream(System.out));
        
        int t = sc.nextint();
        for(int i = 0; i < t; i++) {
        	int n = sc.nextint();
        	Node[] nodes = new Node[n];
        	for(int j = 0; j < n; j++) {
        		nodes[j] = new Node();
        	}
        	for(int j = 1; j < n; j++) {
        		int a = sc.nextint() - 1;
        		int b = sc.nextint() - 1;
        		nodes[a].adj.add(nodes[b]);
        		nodes[b].adj.add(nodes[a]);
        	}
        	int p = sc.nextint();
        	int[] factors = sc.read(p);
        	Arrays.sort(factors);
        	
        	n--;
        	long[] values = new long[n];
        	Arrays.fill(values,  1);
        	for(int j = p-1; j>=0; j--) {
    			int index = Math.max(0, n-j-1);
    			values[index] = (values[index] * (long) factors[j]) % MOD;
    		}
        	
        	long[] edgeWeights = new long[n];
        	nodes[0].dfs(null);
        	for(int j = 1; j <= n; j++) {
        		long times = nodes[j].subTreeSize*(long) (n+1 - nodes[j].subTreeSize);
        		edgeWeights[j-1] = times;
        	}
        	
        	Arrays.sort(edgeWeights);
        	Arrays.sort(values);
        	long ans = 0;
        	for(int j = 0; j < n; j++) {
        		ans = (ans + (edgeWeights[j]*values[j]) % MOD)%MOD; 	
        	}
        	out.println(ans);
        }
        
        
        out.close(); 
    }
    
    
    static class Node{
    	List<Node> adj = new ArrayList<>();
    	int subTreeSize;
    	
    	public void dfs(Node par) {
    		this.subTreeSize = 1;
    		for(Node n : adj) {
    			if(n != par) {
    				n.dfs(this);
    				this.subTreeSize += n.subTreeSize;
    			}
    		}
    	}
    }
    
    private static class FenTree{
    	private long[] tree;
    	public FenTree(int size) {
    		tree = new long[size+1];
    	}
    	
    	public void add(int index, int add) {
    		while(index < tree.length) {
    			tree[index] += add;
    			index += (index & -index);
    		}
    	}
    	
    	public long sum(int index) {
    		long sum = 0;
    		while(index > 0) {
    			sum += tree[index];
    			index -= (index & -index);
    		}
    		
    		return sum;
    	}
    }
    
    public static boolean contains(List<Integer> arr, int key){
        int left = 0;
        int right= arr.size();
        while(left < right){
            int mid = left + (right-left)/2;
            if(arr.get(mid) == key){
                return true;
            }
            else if(arr.get(mid) < key){
                left = mid +1;
            }
            else{
                right = mid;
            }
        }
        return false;
    }
    
    private static long modInverse(long a, long b) {
        long bb = b, temp, q;
        long x0 = 0, x1 = 1;
        if(b == 1){
            return 1L;
        }
        while(a > 1){
            q = a/b;
            temp = b; b = a%b; a=temp;
            temp = x0; x0 = x1-q*x0; x1 = temp;
        }
        if(x1 < 0){
            x1 += bb;
        }
        return x1;
    }
    
    private static int gcd(int a, int b){
        if(a == 0){
            return b;
        }
        return gcd(b%a, a);
    }
    
    private static PrintWriter out;
    private static BufferedReader br;
    private static StringTokenizer st;
    
    private static class FastScanner{
    	public FastScanner() {
    		br = new BufferedReader(new InputStreamReader(System.in));
    	}
    	
    	String next() {
    		while(st == null || !st.hasMoreTokens()) {
    			try {
    				st = new StringTokenizer(br.readLine());
    			}
    			catch (IOException e) {
    				e.printStackTrace();
    			}
    		}
    		return st.nextToken();
    	}
    	
    	int[] read(int n) {
    		int[] res = new int[n];
    		for(int i = 0; i < n; i++) {
    			res[i] = nextint();
    		}
    		return res;
    	}
    	
    	int nextint() {
    		return Integer.parseInt(next());
    	}
    	
    	double nextdouble() {
    		return Double.parseDouble(next());
    	}
    	
    	long nextlong() {
    		return Long.parseLong(next());
    	}
    	
    	String nextline() {
    		String str = "";
    		try {
    			str = br.readLine();
    		}
    		catch (IOException e) {
    			e.printStackTrace();
    		}
    		return str;
    	}
    	
    }
    
}