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


public class Solution{

	static LinkedList<Integer>[] adjList;
	static boolean[] visited;
	static ArrayList<Long> list;
	static int[] count;
	static int n;

	static long MOD = (int)(1e9+7);


	public static void main(String[] args) throws Exception{

		FastScanner fs = new FastScanner();
		int t = fs.nextInt();

		while(t-->0){

			n = fs.nextInt();
			adjList = new LinkedList[n];
			for(int i=0;i<n;i++){
				adjList[i] = new LinkedList<Integer>();
			}
			for(int i=0;i<n-1;i++){
				int u = fs.nextInt()-1, v = fs.nextInt()-1;
				adjList[u].add(v);
				adjList[v].add(u);
			}
			visited = new boolean[n];
			int m = fs.nextInt();
			int[] factors = fs.readArray(m);
			Arrays.sort(factors);

			list = new ArrayList<Long>(n-1);
			count = new int[n];

			dfs(0);

			Collections.sort(list);

			long ans = 0;
			if(m<n-1){
				int i;
				for(i=0;i<n-1-m;i++)
					ans = (ans + list.get(i)%MOD)%MOD;

				for(;i<n-1;i++)
					ans = (ans + (factors[i-n+1+m]*list.get(i))%MOD)%MOD;
			}
			else{
				int i;
				for(i = 0;i<n-2;i++)
					ans = (ans + (factors[i]*list.get(i))%MOD)%MOD;

				long mul = 1L;
				for(;i<m;i++)
					mul =  (mul * factors[i])%MOD;

				ans = (ans + (mul*list.get(n-2))%MOD)%MOD;
			
			}

			System.out.println(ans);

		}
		
	}

	static void dfs(int v){
		visited[v] = true;
		count[v] = 1;

		for(int node: adjList[v]){
			if(!visited[node]){
				dfs(node);
				count[v] += count[node];
			}
		}

		long t = ((long)count[v])*(n-count[v]);
		if(t!=0)
			list.add(t);
	}



	static class FastScanner{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");

		public String next(){
			while(!st.hasMoreElements()){
				try{
					st = new StringTokenizer(br.readLine());
				} catch(IOException e){
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		public int nextInt(){
			return Integer.parseInt(next());
		}

		public int[] readArray(int n){
			int[] a = new int[n];
			for(int i=0;i<n;i++)
				a[i] = nextInt();
			return a;
		}

		public long nextLong(){
			return Long.parseLong(next());
		}

	}

}