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.io.*;
import java.util.*;

public class CF1401D extends PrintWriter {
	CF1401D() { super(System.out); }
	static class Scanner {
		Scanner(InputStream in) { this.in = in; } InputStream in;
		byte[] bb = new byte[1 << 15]; int i, n;
		byte getc() {
			if (i >= n) {
				try { n = in.read(bb); } catch (IOException e) { n = 0; }
				if (n <= 0) return 0;
				i = 0;
			}
			return bb[i++];
		}
		int nextInt() {
			byte c = 0; while (c <= ' ') c = getc();
			int a = 0; while (c > ' ') { a = a * 10 + c - '0'; c = getc(); }
			return a;
		}
	}
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF1401D o = new CF1401D(); o.main(); o.flush();
	}

	static final int MD = 1000000007;
	int[] oo; int[][] oh;
	int[] ij; long[] kk;
	void append(int i, int h) {
		int o = oo[i]++;
		if (o >= 2 && (o & o - 1) == 0)
			oh[i] = Arrays.copyOf(oh[i], o << 1);
		oh[i][o] = h;
	}
	void init(int n) {
		oo = new int[n]; oh = new int[n][2];
		ij = new int[n]; kk = new long[n];
	}
	void dfs(int h_, int i) {
		int k = 1;
		for (int o = 0; o < oo[i]; o++) {
			int h = oh[i][o];
			if (h != h_) {
				int j = i ^ ij[h];
				dfs(h, j);
				k += kk[h];
			}
		}
		kk[h_] = k;
	}
	void main() {
		int t = sc.nextInt();
		while (t-- > 0) {
			int n = sc.nextInt();
			init(n);
			for (int h = 1; h < n; h++) {
				int i = sc.nextInt() - 1;
				int j = sc.nextInt() - 1;
				ij[h] = i ^ j;
				append(i, h);
				append(j, h);
			}
			int m = sc.nextInt();
			int m_ = Math.max(m, n - 1);
			int[] pp = new int[m_];
			for (int h = 0; h < m; h++)
				pp[h] = sc.nextInt();
			for (int h = m; h < m_; h++)
				pp[h] = 1;
			pp = Arrays.stream(pp).boxed().sorted().mapToInt($->$).toArray();
			while (m > n - 1) {
				pp[m - 2] = (int) ((long) pp[m - 2] * pp[m - 1] % MD);
				m--;
			}
			dfs(0, 0);
			for (int h = 0; h < n - 1; h++) {
				long k = kk[h + 1];
				kk[h] = (n - k) * k;
			}
			kk = Arrays.stream(kk, 0, n - 1).boxed().sorted((a, b) -> Long.signum(a - b)).mapToLong($->$).toArray();
			long ans = 0;
			for (int h = 0; h < n - 1; h++) {
				long k = kk[h] % MD;
				ans = (ans + k * pp[h]) % MD;
			}
			println(ans);
		}
	}
}
