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.*;
/*
1
4
1 2
2 3
3 4
11
2 2 2 2 2 3 3 7 109 109 167


 */











public class C {
    static FastReader sc=null;
    static long mod=(long)1e9+ 7;
    static int n;
    static Edge[] edges;
    static int count;
    
    public static void main(String[] args) {
		sc=new FastReader();
		int t=sc.nextInt();
		while(t-->0) {
			n=sc.nextInt();
			Node nodes[]=new Node[n];
			for(int i=0;i<n;i++)nodes[i]=new Node(i);
			for(int i=0;i+1<n;i++) {
				int v=sc.nextInt()-1,w=sc.nextInt()-1;
				nodes[v].adj.add(nodes[w]);
				nodes[w].adj.add(nodes[v]);
			}
			count=0;
			edges=new Edge[n-1];
			for(int i=0;i+1<n;i++)edges[i]=new Edge();
			dfs(nodes[0],null);
			Arrays.sort(edges);
			long values[]=new long[n-1];
			int m=sc.nextInt();
			int a[]=sc.readArray(m);
			ruffleSort(a);
			if(m<=n-1) {
				for(int i=0;i<m;i++)values[i]=a[i];
				for(int i=m;i<n-1;i++)values[i]=1;
				ruffleSort(values);
			}
			else{
				for(int i=0;i<n-2;i++) {
					values[i]=a[i];
				}
				values[n-2]=1;
				for(int i=n-2;i<m;i++)values[n-2]=mul(values[n-2],a[i]);
			}
			long ans=0;
			long edgeWeights[]=new long[n-1];
			for(int i=0;i+1<n;i++)edgeWeights[i]=edges[i].val;
			//print(values);
			//print(edgeWeights);
			//for(Node nn:nodes)System.out.print(nn.subTreeSize+" ");
			//System.out.println();
			
			for(int i=0;i+1<n;i++) {
				ans=add(ans,mul(values[i],edges[i].val));
			}
			System.out.println(ans);
			
		}
		
		
		
	
	}
    static long add(long a,long b) {
		return (a%mod+b%mod)%mod;
	}
	static long mul(long a ,long b) {
		return ((a%mod)*(b%mod)+mod)%mod;
	}
    static void dfs(Node v,Node par) {
    	for(Node nn:v.adj) {
    		if(nn!=par) {
    			dfs(nn,v);
    			v.subTreeSize+=nn.subTreeSize;
    		}
    	}
    	if(v.subTreeSize!=n) {
    	    edges[count].val=(long)v.subTreeSize*(n-v.subTreeSize);
    		count++;
    	}
    }
    static class Edge implements Comparable<Edge>{
    	long val=0;
		@Override
		public int compareTo(Edge o) {
			return Long.compare(this.val, o.val);
		}
    }
    static class Node{
    	int id;
    	int subTreeSize=1;
    	long ans=1;
    	ArrayList<Node> adj=new ArrayList<>();
    	Node(int id){
    		this.id=id;
    	}
		
    }
   
   
    
  
    
    static void ruffleSort(int a[]) {
        ArrayList<Integer> al=new ArrayList<>();
        for(int i:a)al.add(i);
        Collections.sort(al);
        for(int i=0;i<a.length;i++)a[i]=al.get(i);
    }
    static void ruffleSort(long a[]) {
        ArrayList<Long> al=new ArrayList<>();
        for(long i:a)al.add(i);
        Collections.sort(al);
        for(int i=0;i<a.length;i++)a[i]=al.get(i);
    }
    
    static int[] reverse(int a[]) {
        ArrayList<Integer> al=new ArrayList<>();
        for(int i:a)al.add(i);
        Collections.sort(al,Collections.reverseOrder());
        for(int i=0;i<a.length;i++)a[i]=al.get(i);
        return a;
    }
 
    static int gcd(int a,int b) {
		if(b==0)return a;
		else return gcd(b,a%b);
	}  
    static long gcd(long a,long b) {
		if(b==0)return a;
		else return gcd(b,a%b);
	}  
        
 
    
    
    
    static void print(long a[]) {
        for(long e:a) {
            System.out.print(e+" ");
        }
        System.out.println();
    }
    static void print(char a[]) {
        for(char e:a) {
            System.out.print(e);
        }
        System.out.println();
    }
    
    
    static void print(int a[]) {
        for(int e:a) {
            System.out.print(e+" ");
        }
        System.out.println();
    }
    
    
    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; 
        } 
        int[] readArray(int n) {
            int a[]=new int [n];
            for(int i=0;i<n;i++) {
                a[i]=sc.nextInt();
            }
            return a;
        }
    } 
}
