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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Map.Entry;

import java.util.Random;
import java.util.TreeSet;

public final class CF_665_D2_D
{


	static boolean verb=true;
	static void log(Object X){if (verb) System.err.println(X);}
	static void log(Object[] X){if (verb) {for (Object U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X){if (verb) {for (int U:X) System.err.print(U+" ");System.err.println("");}}
	static void logWln(int[] X){if (verb) {for (int U:X) System.err.print(U+" ");}}
	static void log(int[] X,int L){if (verb) {for (int i=0;i<L;i++) System.err.print(X[i]+" ");System.err.println("");}}
	static void log(long[] X){if (verb) {for (long U:X) System.err.print(U+" ");System.err.println("");}}

	static void logWln(Object X){if (verb) System.err.print(X);}
	static void info(Object o){	System.out.println(o);}
	static void output(Object o){outputWln(""+o+"\n");	}
	static void outputFlush(Object o){try {out.write(""+ o+"\n");out.flush();} catch (Exception e) {}}
	static void outputWln(Object o){try {out.write(""+ o);} catch (Exception e) {}}


	static void logBin(int[] tm) {for (int x:tm) logWln(bin(8,x)+" ");log("");}

	static String bin(int L,int x) {
		String s=Integer.toBinaryString(x);
		while (s.length()<L) s="0"+s;
		return s;
	}

	static long powerMod(long b,long e,long m){
		long x=1;
		while (e>0) {
			if (e%2==1)
				x=(b*x)%m;
			b=(b*b)%m;
			e=e/2;
		}
		return x; 
	}


	static class Composite implements Comparable<Composite>{

		int val;
		int idx;


		public int compareTo(Composite X) {
			if (val!=X.val)
				return val-X.val;
			return idx-X.idx;
		}


		public Composite(int val, int idx) {
			this.val = val;
			this.idx = idx;
		}







	}
	
	static long mod=1000000007;
	
	
	static int[][] friends;
	static int[] stack;
	static int[] visited;
	static int time;
	static int[] anc;
	static int[] cnt;
	static int[] from,to,ptr;
	static long[] bob;
	
	static long dfs(int n,int src,long[] p){
		int st=0;
		time++;
		Arrays.fill(anc, -1);
		stack[st++]=src;
		
		while (st>0) {
			int u=stack[st-1];
			if (visited[u]<time) {
				visited[u]=time;
				for (int v:friends[u]) {
					if (v!=anc[u]) {
						stack[st++]=v;
						anc[v]=u;
					}
				}
			} else {
				st--;
				cnt[u]=1;
				for (int v:friends[u]) {
					if (v!=anc[u]) {
						cnt[u]+=cnt[v];
					}
				}
				
			}
		}
		Arrays.fill(bob,0);
		for (int u=1;u<n;u++) {
			long below=cnt[u];
			long above=n-cnt[u];
			bob[u-1]=below*above;
			
		}
		Arrays.parallelSort(bob,0,n-1);
		Arrays.parallelSort(p);
		for (int i=0;i<n-1;i++)
			if (bob[i]>=mod)
				bob[i]%=mod;
		int m=p.length;
		long res=0;
		if (m>=n-1) {
			for (int i=0;i<n-2;i++) {
				long delta=bob[i]*p[i];
				if (delta>=mod)
					delta%=mod;
				res+=delta;
				if (res>=mod)
					res-=mod;
			}
			long delta=bob[n-2];
			for (int i=n-2;i<m;i++) {
				delta*=p[i];
				if (delta>=mod)
					delta%=mod;
			}
			res+=delta;
			if (res>=mod)
				res-=mod;
			
		} else {
			int d=n-1-m;
			for (int i=0;i<d;i++) {
				res+=bob[i];
				if (res>=mod)
					res-=mod;
			}
			for (int i=d;i<n-1;i++) {
				long delta=bob[i]*p[i-d];
				if (delta>=mod)
					delta%=mod;
				res+=delta;
				if (res>=mod)
					res-=mod;
			}
		}
		return res;
		
	}

	// Global vars
	static BufferedWriter out;
	static InputReader reader;

	static int[][] dd={{-1,0},{0,1},{1,0},{0,-1}};
	
	static int CX=26;


	static void process() throws Exception {

		out = new BufferedWriter(new OutputStreamWriter(System.out));
		reader = new InputReader(System.in);

	int T=reader.readInt();
	int NX=100001;
	stack=new int[NX];
	cnt=new int[NX];
	visited=new int[NX];
	anc=new int[NX];
	time=1;
	friends=new int[NX][];
	from=new int[NX];
	to=new int[NX];
	ptr=new int[NX];
	bob=new long[NX];
	
	for (int t=0;t<T;t++) {
	
		int n=reader.readInt();
		
		for (int i=0;i<n-1;i++) {
			int u=reader.readInt()-1;
			int v=reader.readInt()-1;
			from[i]=u;
			to[i]=v;
			ptr[u]++;
			ptr[v]++;
		}
	
		for (int u=0;u<n;u++)
			friends[u]=new int[ptr[u]];
		for (int i=0;i<n-1;i++) {
			friends[from[i]][--ptr[from[i]]]=to[i];
			friends[to[i]][--ptr[to[i]]]=from[i];
		}
		int m=reader.readInt();
		long[] p=new long[m];
		for (int i=0;i<m;i++)
			p[i]=reader.readLong();
		output(dfs(n,0,p));
		
	}


		try {
			out.close();
		} catch (Exception Ex) {
		}

	}




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

	}

	static final class InputReader {
		private final InputStream stream;
		private final byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		private int read() throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read(buf);
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}

		public final String readString() throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.append((char) c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final String readString(int L) throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder(L);
			do {
				res.append((char) c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final int readInt() throws IOException {
			int c = read();
			boolean neg = false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d = (char) c;
			// log("d:"+d);
			if (d == '-') {
				neg = true;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			// log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		public final long readLong() throws IOException {
			int c = read();
			boolean neg = false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d = (char) c;
			// log("d:"+d);
			if (d == '-') {
				neg = true;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			// log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}

}