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.text.DecimalFormat;
import java.util.*;
public class Main {
	
	public static long GCD(long i, long j){
	if (i==0){
		return j;
	}
	return GCD(j%i,i);
	}
	public static long LCM(long i, long j){
		return(i*j)/GCD(i,j);
	}
	public static String inc(long[] a){
		boolean b=true;
		for(int i=0;i<a.length-1;i++){
			
			if(a[i]>a[i+1]){
				b=false;
				break;
			}
		}
		if(b){
		return "YES";
		}
		else{
			return "NO";
		}
	}
public static long min(long[] a){
	long res=Integer.MAX_VALUE;
	for(int i=0;i<a.length;i++){
		res=Math.min(res, a[i]);
	}
	return res;
}
	public static void main(String[] args) throws Exception {
	Scanner sc=new Scanner(System.in);
int t=sc.nextInt();

while(t-->0){
 n=sc.nextInt();
 adjlist=(ArrayList<Integer>[]) new ArrayList [n];
 edges=new edge [n-1];
 freq=new int[n];
for(int i=0;i<n;i++){
	adjlist[i]=new ArrayList<Integer>();
	
}
for(int i=0;i<n-1;i++){
	int u=sc.nextInt()-1;
	int v=sc.nextInt()-1;
	adjlist[u].add(v);
	adjlist[v].add(u);
	edges[i]=new edge(u,v,1);
	
}
int m=sc.nextInt();
PriorityQueue <Long> fact=new PriorityQueue<>(Collections.reverseOrder());
 e=new PriorityQueue<>(Collections.reverseOrder());
for(int i=0;i<m;i++){
	fact.add(sc.nextLong());
}
for(int i=m;i<n-1;i++){
	fact.add(1l);
}
dfs(0,-1);

long res=0;
long c=1;
while(fact.size()!=n-2){
	
 c=((c%mod)*fact.poll()%mod)%mod;

	
}

long curr=((e.poll()%mod)*(c%mod))%mod;
res=(res+(curr)%mod)%mod;

for(int i=1;i<n-1;i++){
	
	 curr=((e.poll()%mod)*(fact.poll()%mod))%mod;
	res=(res+(curr)%mod)%mod;
}
System.out.println(res);
}
 
	}
	static PriorityQueue <Long> e;
	static int n;
	static long mod=1000000007;
	static edge [] edges;
	 static ArrayList<Integer>[] adjlist;
	 static int[] freq;
	static class edge implements Comparable<edge>
	{
		int  u;
		int v;
		long p;
		public edge(int u,int v,long p){
			this.u=u;
			this.v=v;
			this.p=p;
		}
		public long freq(){
			return ((n-Math.min(freq[u], freq[v])%mod)*(Math.min(freq[u], freq[v])%mod)%mod);
			
		}
		@Override
		public int compareTo(edge e) {
			// TODO Auto-generated method stub
			return Long.compare(freq(),e.freq());
		}
		
	}
	public static long dfs(int u, int p){
	
		long ans =1;
		for(int x:adjlist[u]){
			if(x!=p){
				long num=dfs(x,u);
				e.add(num*(n-num));
			     ans+=num;
			}
		}
		return ans;
	}
	  	 	static class SegmentTree{
	   	 		int[] arr , sTree;
	   	 	static	int N;
	   	 		public SegmentTree(int[] in){
	   	 			arr=in;
	   	 		N=arr.length-1;
	   	 			sTree=new int[2*N];
	   	 			
	   	 			build(1,1,N);
	   	 		}
	   	 		public void build(int node, int l, int r){
	   	 			if(l==r){
	   	 				sTree[node]=arr[l];
	   	 			}
	   	 			else{
	   	 				int leftchild=node*2;
	   	 				int rightchild=node*2+1;
	   	 				int mid =(l+r)/2;
	   	 				build(leftchild,l,mid);
	   	 				build(rightchild,mid+1,r);
	   	 				sTree[node]=sTree[leftchild]&sTree[rightchild];
	   	 			}
	   	 		}
	   	 		public  void update(int i, int val){
	   	 			int node =i+N-1;
	   	 			arr[i]=val;
	   	 			sTree[node]=val;
	   	 			node=node/2;
	   	 			while(node>0){
	   	 			int leftchild=node *2;
   	 				int rightchild=node*2+1;
   	 			sTree[node]=sTree[leftchild]&sTree[rightchild];
   	 			node=node/2;
	   	 			}
	   	 			return;
	   	 			
	   	 		}
	   	 		public int query(int i, int j){
	   	 			 return query(1,1, N,  i, j);
	   	 		}
	   	 		public int query(int node,int l, int r, int i , int j){
	   	 			if(i>r||j<l){
	   	 				return 1<<30;
	   	 			}
	   	 			if(i<=l&&r<=j){
	   	 				return sTree[node];
	   	 			}
	   	 		int leftchild=node*2;
	 				int rightchild=node*2+1;
	 				int mid =(l+r)/2;
	 				
	 			return	query(leftchild,l,mid,i,j)&query(rightchild,mid+1,r,i,j);
	 				
	   	 		}
	   	 	}
 
 
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;
 
		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}
 
		public boolean hasNext() {
			// TODO Auto-generated method stub
			return false;
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
	}}