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.math.BigInteger;
							import java.util.ArrayList;
							import java.util.Arrays;
						import java.util.Collection;
						import java.util.Collections;
						import java.util.Comparator;
						import java.util.HashMap;
							import java.util.Iterator;
						import java.util.LinkedList;
						import java.util.List;
						import java.util.Map;
					import java.util.Map.Entry;
					import java.util.PriorityQueue;
						import java.util.Scanner;
						import java.util.Set;
						import java.util.Stack;
						import java.io.BufferedReader; 
						import java.io.IOException; 
						import java.io.InputStreamReader; 
						import java.util.Scanner; 
						import java.util.StringTokenizer;
						import java.util.TreeMap;
						import java.util.TreeSet;
						
							public class Main {
							
								static FastReader sc= new FastReader();
								static List<Integer> C;
								static List<Integer> B;
							static	int mod=(int)1e9+9;
								static long dp[];
								static int k;
								static boolean prime[] = new boolean[100001]; 
								public static void main(String[] args) {

										int t=sc.nextInt();
										
										
										
										while(t-->0) {
											
										int n=sc.nextInt();
										
										ArrayList<Integer> tree[]=new ArrayList[n+1];
										  for(int i=1;i<=n;i++) {
											  tree[i]=(new ArrayList<Integer>());
										  }
										 for(int i=0;i<n-1;i++) {
											  int a=sc.nextInt();
											  int b=sc.nextInt();
											  tree[a].add(b);
											  tree[b].add(a);
										  }
										 
										 
										 long sts[]=new long[n+1];
										  Arrays.fill(sts, 1);
										  k=0;
										  long afe[]=new long[n];
										 dfs(1,0,tree,sts,afe,n);
										  int m=sc.nextInt();
										  long a[]=new long[m];
										  for(int i=0;i<m;i++) {
											  a[i]=sc.nextLong();
										  }
										 Arrays.sort(a);
										 
										 Arrays.sort(afe);
										 
										// for(int i=0;i<n;i++)System.out.print(afe[i]+" ");
										 long total=0;
										 if(m>n-1) {
											 int i=0;
											 for( i=1;i<n-1;i++) {
												total=(long) ((total+(a[i-1]*afe[i])%(1e9+7))%(1e9+7));
												 
												 
											 }
											 long k=1;
											 for(;i<m+1;i++) {
													k=(long) ((k*a[i-1])%(long)(1e9+7));
													 
													 
												 }
											 total=(long) ((total+(k*afe[n-1])%(long)(1e9+7))%(long)(1e9+7));
											 
										 }
										 else {
											 int i=0;
											 int j=n-1;
											 for( i=m-1;i>=0;i--) {
												total=(long) (total+((a[i]*afe[j--])%(long)(1e9+7))%(long)(1e9+7));
												 
												 
											 }
											 int k=0;
											 for(;j>=0;j--) {
													total=(long) ((total+afe[j])%(long)(1e9+7));
													 
													 
												 }
											 
											
											 
											 
										 }
										 System.out.println(total%(int)(1e9+7));
											
								
											
								}
								}
								static void dfs(int node, int parent, ArrayList<Integer> al[], long sts[], long afe[], int n) {
									for(int c:al[node]) {
										if(c!=parent) {
											dfs(c,node,al,sts,afe,n);
											sts[node]=(sts[node]+sts[c]);
										}
									}
//									System.out.println(k++);
									afe[k++]=(n-sts[node])*sts[node];
								}
							 
								
								
								 static int gcd(int a, int b) 
								    { 
								      if (b == 0) 
								        return a; 
								      return gcd(b, a % b);  
								    } 
								
								 static final int MAXN = 100001; 
							       
								    // stores smallest prime factor for every number 
								    static int spf[] = new int[MAXN]; 
								       
								    // Calculating SPF (Smallest Prime Factor) for every 
								    // number till MAXN. 
								    // Time Complexity : O(nloglogn) 
								    static void sieve() 
								    { 
								        spf[1] = 1; 
								        for (int i=2; i<MAXN; i++) 
								       
								            // marking smallest prime factor for every 
								            // number to be itself. 
								            spf[i] = i; 
								       
								        // separately marking spf for every even 
								        // number as 2 
								        for (int i=4; i<MAXN; i+=2) 
								            spf[i] = 2; 
								       
								        for (int i=3; i*i<MAXN; i++) 
								        { 
								            // checking if i is prime 
								            if (spf[i] == i) 
								            { 
								                // marking SPF for all numbers divisible by i 
								                for (int j=i*i; j<MAXN; j+=i) 
								       
								                    // marking spf[j] if it is not  
								                    // previously marked 
								                    if (spf[j]==j) 
								                        spf[j] = i; 
								            } 
								        } 
								    } 
								        
								
							static	 void sieveOfEratosthenes(int n) 
								    { 
								        // Create a boolean array "prime[0..n]" and initialize 
								        // all entries it as true. A value in prime[i] will 
								        // finally be false if i is Not a prime, else true. 
								        //boolean prime[] = new boolean[n+1]; 
								        for(int i=0;i<n;i++) 
								            prime[i] = true; 
								          
								        for(int p = 2; p*p <=n; p++) 
								        { 
								            // If prime[p] is not changed, then it is a prime 
								            if(prime[p] == true) 
								            { 
								                // Update all multiples of p 
								                for(int i = p*p; i <= n; i += p) 
								                    prime[i] = false; 
								            } 
								        } 
								          
								        
								       // System.out.println(n);
								    } 
								
								
								
								
								static long  solve(List<Integer> A,int n,long cost,int k,HashMap<Integer,  Integer> map) {
									//if(!map.containsKey(curr))map.put(curr,);
									//if(n==0&&curr!=0)return 1;
									if(dp[n]!=-1)return dp[n];
									if(n==0)return cost;
					//				if(dp[n]!=-1)return dp[n];
								//	if(dp[n]!=-1)return dp[n];
	
					
									if(map.containsKey(C.get(n-1))) {
										
										long addon=0l;
										if(map.get(C.get(n-1))==1)addon=2l;
										else addon=1l;
										
										map.put(C.get(n-1),map.get(C.get(n-1))+1);
										//System.out.println(cost+" "+n+" "+map);
										return dp[n]=Math.min(solve(A,n-1,cost+addon,k,map),solve(A, n-1,k+cost,k, new HashMap<Integer,Integer>(C.get(n-1),1)));
										
									}
									else {map.put(C.get(n-1), 1); return dp[n] =solve(A,  n-1, cost,k, map);
									}
									
								}
								
					
								
								
								
							static int exponentMod(int A,  
					                       int B, int C)  
					{  
					          
					    // Base cases  
					    if (A == 0)  
					        return 0;  
					    if (B == 0)  
					        return 1;  
					      
					    // If B is even  
					    long y;  
					    if (B % 2 == 0) 
					    {  
					        y = exponentMod(A, B / 2, C);  
					        y = (y * y) % C;  
					    }  
					      
					    // If B is odd  
					    else 
					    {  
					        y = A % C;  
					        y = (y * exponentMod(A, B - 1,  
					                             C) % C) % C;  
					    }  
					      
					    return (int)((y + C) % C);  
					}  
								
							static	int modulo(int a,int b,int c) {
								    long x=1;
								    long y=a;
								    while(b > 0){
								        if(b%2 == 1){
								            x=(x*y)%c;
								        }
								        y = (y*y)%c; // squaring the base
								        b /= 2;
								    }
								    return (int) x%c;
								}
								
								 static int power(int x, int y, int p) 
								    { 
								        // Initialize result 
								        int res = 1;      
								         
								        // Update x if it is more   
								        // than or equal to p 
								        x = x % p;  
								  
								       if (x == 0) return 0; // In case x is divisible by p;    
								  
								        while (y > 0) 
								        { 
								            // If y is odd, multiply x 
								            // with result 
								            if((y & 1)==1) 
								                res = (res * x) % p; 
								      
								            // y must be even now 
								            // y = y / 2 
								            y = y >> 1;  
								            x = (x * x) % p;  
								        } 
								        return res; 
								    }
								static int N = 100000;  
							      
							    static int n; // array size 
							      
							    // Max size of tree 
							    static int []tree = new int[2 * N]; 
										
								 static void build( int []arr)  
								    {  
								          
								        // insert leaf nodes in tree 
								        for (int i = 0; i < n; i++)  
								            tree[n + i] = arr[i]; 
								          
								        // build the tree by calculating 
								        // parents 
								        for (int i = n - 1; i > 0; --i)  
								            tree[i] = tree[i << 1] + 
								                      tree[i << 1 | 1];  
								    } 
								      
								    // function to update a tree node 
								    static void updateTreeNode(int p, int value)  
								    {  
								          
								        // set value at position p 
								        tree[p + n] = value; 
								        p = p + n; 
								          
								        // move upward and update parents 
								        for (int i = p; i > 1; i >>= 1) 
								            tree[i >> 1] = tree[i] + tree[i^1]; 
								    } 
								      
								    // function to get sum on 
								    // interval [l, r) 
								    static int query(int l, int r)  
								    {  
								        int res = 0; 
								          
								        // loop to find the sum in the range 
								        for (l += n, r += n; l < r; 
								                             l >>= 1, r >>= 1) 
								        { 
								            if ((l & 1) > 0)  
								                res += tree[l++]; 
								          
								            if ((r & 1) > 0)  
								                res += tree[--r]; 
								        } 
								          
								        return res; 
								    } 
								      
									
								
								
								static int a=1;
								
											
								
							static class decimal{
								int n;double d;
								public decimal(int n,double d) {
									
									this.n=n;
									this.d=d;
									// TODO Auto-generated constructor stub
								}
							}
								
							static	boolean isPossible(List<Integer> C,int m,int k) {
									if(m==0)return false;
									for(int i=0;i<C.size();i++) {
										
										if(C.get(i)>m) {
											k-=C.get(i)/m;
										}
										if(k<0)return false;
									}
										return true;
									
									
								}
								  
								
								
								
								static boolean isSubsetSum(int set[],  int n, int sum) 
						{ 
						// The value of subset[i][j] will be 
						// true if there is a subset of 
						// set[0..j-1] with sum equal to i 
						boolean subset[][] = new boolean[sum + 1][n + 1]; 
						
						// If sum is 0, then answer is true 
						for (int i = 0; i <= n; i++) 
						subset[0][i] = true; 
						
						// If sum is not 0 and set is empty, 
						// then answer is false 
						for (int i = 1; i <= sum; i++) 
						subset[i][0] = false; 
						
						// Fill the subset table in botton 
						// up manner 
						for (int i = 1; i <= sum; i++) { 
						for (int j = 1; j <= n; j++) { 
						    subset[i][j] = subset[i][j - 1]; 
						    if (i >= set[j - 1]) 
						        subset[i][j] = subset[i][j] 
						                       || subset[i - set[j - 1]][j - 1]; 
						} 
						} 
						
						
						return subset[sum][n]; 
						} 
						
						
								
								
								static boolean search(ArrayList<Integer> a,int m,int h) {
									PriorityQueue<Integer> p=new PriorityQueue<Integer>(new Comparator<Integer>() {
											@Override
											public int compare(Integer o1, Integer o2) {
												// TODO Auto-generated method stub
												return o2-o1;
											}
									});
									
									
									
									for(int i=0;i<m;i++) {
										p.add(a.get(i));
									}
									int c=0;
									//System.out.println(p);
									while(!p.isEmpty()) {
										//System.out.println(p);
						
										h-=p.poll();
										if(h<0)break;
										
										c++;
										
									//	System.out.println(h+" "+p+" "+c+" "+m);
						
										if(!p.isEmpty()) {
										p.poll();
										c++;}
										
										
									}
								//	System.out.println(c!=m);
									if(c!=m)return false;
									
									return true;
								}
							//	static int  key=-1;
								
								
								
								
								
								
								static boolean isPowerOfTwo(long n) 
							    { 
							        if (n == 0) 
							            return false; 
							          
							        while (n != 1) 
							        { 
							            if (n % 2 != 0) 
							                return false; 
							            n = n / 2; 
							        } 
							        return true; 
							    } 
								
								 static boolean isPerfectSquare(double x)  
								    { 
								          
								        // Find floating point value of 
								        // square root of x. 
								        double sr = Math.sqrt(x); 
								      
								        // If square root is an integer 
								        return ((sr - Math.floor(sr)) == 0); 
								    } 
								
								
								
								
								
								
							static	int binarySearch(ArrayList<Long> arr, int l, int r, long x,int key) 
							    { 
							        if (r >= l) { 
							            int mid =  (r + l) / 2; 
							//  if(mid>=arr.size())return -1;
							            // If the element is present at the 
							            // middle itself 
							  			
							            if (arr.get(mid) == x) 
							                return mid+1; 
							  
							            // If element is smaller than mid, then 
							            // it can only be present in left subarray 
							            if (arr.get(mid) > x) {
							                return binarySearch(arr, l, mid - 1, x,key); 
							            }
							            // Else the element can only be present 
							            // in right subarray
							            key=mid+1;
							            return binarySearch(arr, mid + 1, r, x,key); 
							        } 
							  
							        // We reach here when element is not present 
							        // in array 
							        return key; 
							    } 
								
								
								
								
								
								
								
								
							    static boolean isPrime(long n) 
							    { 
							         // Corner cases 
							        if (n <= 1) 
							            return false; 
							        if (n <= 3) 
							            return true; 
							  
							        // This is checked so that we can skip 
							        // middle five numbers in below loop 
							        if (n % 2 == 0 || n % 3 == 0) 
							            return false; 
							  
							        for (int i = 5; i * i <= n; i = i + 6) 
							            if (n % i == 0 || n % (i + 2) == 0) 
							                return false; 
							  
							        return true; 
							    } 
							    
							    
							    
							    static class FastReader 
							    { 
							        BufferedReader br; 
							        StringTokenizer st; 
							  
							        public FastReader() 
							        { 
							            br = new BufferedReader(new
							                     InputStreamReader(System.in)); 
							        } 
							  
							        String next() 
							        { 
							            while (st == null || !st.hasMoreElements()) 
							            { 
							                try
							                { 
							                    st = new StringTokenizer(br.readLine()); 
							                } 
							                catch (IOException  e) 
							                { 
							                    e.printStackTrace(); 
							                } 
							            } 
							            return st.nextToken(); 
							        } 
							  
							        int nextInt() 
							        { 
							            return Integer.parseInt(next()); 
							        } 
							  
							        long nextLong() 
							        { 
							            return Long.parseLong(next()); 
							        } 
							  
							        double nextDouble() 
							        { 
							            return Double.parseDouble(next()); 
							        } 
							  
							        String nextLine() 
							        { 
							            String str = ""; 
							            try
							            { 
							                str = br.readLine(); 
							            } 
							            catch (IOException e) 
							            { 
							                e.printStackTrace(); 
							            } 
							            return str; 
							        } 
							    } 
								
								
									
							}
							
							class Sol {
								
								int value;int in;int i;
								Sol(int value,int in,int i){
									this.value=value;
									this.in=in;
									this.i=i;
								}
								
						}
					
					 class SegmentTree {
						
						SegNode st[];
						int n;
					//	long arr[];
						public SegmentTree(int n) {
								this.n=n;
							//this.arr=arr;
							st=new SegNode[4*n];
								
						}
						
						void init(long n) {
							
							for(int i=0;i<4*n;i++) {
								st[i]=new SegNode();
							}
							
						}
						
						void set(int i,long v,int x,int lx,int rx) {
							
							if(rx-lx==1) {
								st[x].sum=v;
								st[x].max=v;
								return ;
							}
							int m=lx+(rx-lx)/2;
							if(i<m) set(i,v,2*x+1,lx,m);
							else set(i,v,2*x+2,m,rx); 
							
							st[x].sum=st[2*x+1].sum+st[2*x+2].sum;
							long ma=Math.max(st[2*x+1].max,st[2*x+2].max);
								st[x].max=Math.max(ma,st[x].sum);
						}
						
						void set (int i,long v) {
							set(i,v,0,0,n);
						}
						
						long max=Integer.MIN_VALUE;
					long sum(int l,int r,int x,int lx,int rx) {
						if(lx>=r||l>=rx)return 0;
						if(lx>=l||rx<=r)return st[x].sum;
						
							int m=(rx+lx)/2;
							
							long s1=sum(l,r,2*x+1,lx,m);
							long s2=sum(l,r,2*x+2,m,rx); 	
							
							return max= Math.max(Math.max(Math.max(s1,s2),s1+s2),max);
							
						
						}
						long sum(int l,int r) {
							return sum(l,r,0,0,n);
						}
						
						
					
						
						
						
						
						
						
					
					}
						class SegNode{
							long max;long sum;
							public SegNode() {
								// TODO Auto-generated constructor stub
								sum=0;
								max=Integer.MIN_VALUE;
								
							}
						}
							
							
							
							
