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 java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

//https://codeforces.com/contest/1401/problem/D

public class Solution {
	static long mod = 1000000007;
	static int[] primes = new int[6*10000];
	//static int[]subTree = new int[100000];
	static boolean[]visited = new boolean[100000];
	static long[] weights = new long[100000];
	static int numNodes;
	public static void main(String[] args) {
		int t,n, m,k;
		Scanner sc = new Scanner(System.in);
		t= sc.nextInt();
		for(int i = 0 ; i < t; i++) {
			n = sc.nextInt();
			numNodes = n;
			ArrayList<ArrayList<Integer>> adjList = new ArrayList<ArrayList<Integer>>();
			for(int j = 1 ; j <= n ; j++) {
				adjList.add(new ArrayList<Integer>());
			}
			int src, dest;
			for(int j = 1; j <= n-1; j++ ) {
				src = sc.nextInt();
				dest = sc.nextInt();
				visited[src - 1] = false;
				visited[dest - 1] = false;
				adjList.get(src-1).add(dest-1);
				adjList.get(dest-1).add(src-1);
			}
			
			m = sc.nextInt();
			for(int j = 0 ; j < m ; j++) {
				primes[j] = sc.nextInt();
			}
			
			
			dfs(0, adjList);
			Arrays.sort(primes, 0, m);
			Arrays.sort(weights, 0, n);
			
			//case 1: number of primes (m) >= number of edges (n-1)
			long res = 0;
			if(m >= n-1) {
				for(int j = 1 ; j <= n-2 ; j++) {
					res = (res + (primes[j-1]*weights[j]) % mod) % mod;
				}
				long prod = 1;
				for(int j = n-2 ; j < m ; j++ ) {
					prod = (prod * primes[j])  % mod;
				}
				//System.out.println(weights[n-1]);
				res = (res + (prod * weights[n-1]  % mod)) % mod;
			} else {
				int diff = n -1 -m;
				int off = diff+1;
				for(int j = off; j <= n -1 ; j++) {
					
					//System.out.println("j " + j + " weights[j] " + weights[j]);
					//System.out.println("j-off "+ " primes[j - diff] " + primes[j - off]);
					res = (res + weights[j] * primes[j - off]% mod) % mod;
				}
				for(int j = 1 ; j < off; j++) {
					//System.out.println("weights[j] "+weights[j]);
					res = (res + weights[j]) % mod;
				}
			}
			System.out.println(res);
		}
	}
	private static int  dfs(int i, ArrayList<ArrayList<Integer>> adjList) {
		visited[i] = true;
		ArrayList<Integer> adj = adjList.get(i);
		int subNodes = 0,subTree;
		for(int v = 0 ; v < adj.size(); v++) {
			int vert = adj.get(v);
			if(visited[vert] == false) {
				subNodes = subNodes + dfs(vert, adjList);
			}
			
		}
		subTree = 1 + subNodes;
		weights[i] = (numNodes * 1L - subTree) *subTree;
		return subTree;
	}
}
