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 javax.crypto.AEADBadTagException;
import java.io.*;
import java.util.*;

public class TaskD {


    static class Edge {
        int x;
        int y;
        long pow;
        Edge(int a, int b) {
            x = a;
            y = b;
        }
    }

    static ArrayList<Integer>[] adj;
    static int n;
    static ArrayList<Long> al;

    public static void main(String[] args) throws Exception {
        Reader sc = new Reader();
        PrintWriter pw = new PrintWriter(System.out);

        
        try {
            int t = sc.nextInt();
            while(t-->0) {
                al = new ArrayList<>();
                n = sc.nextInt();
                adj = new ArrayList[n];
                Edge[] e = new Edge[n-1];
                for(int i=0 ; i<n ; i++) adj[i] = new ArrayList<>();
                for(int i=0 ; i<n-1 ; i++) {
                    int u = sc.nextInt()-1;
                    int v = sc.nextInt()-1;
                    adj[u].add(v);
                    adj[v].add(u);
                    e[i] = new Edge(u, v);
                }

                dfs(0, -1);

                int m = sc.nextInt();
                int[] a = new int[m];
                for(int i=0 ; i<m ; i++) {
                    a[i] = sc.nextInt();
                }
                Arrays.sort(a);
                for(int i=0 ; i<m/2 ; i++) {
                    int temp = a[i];
                    a[i] = a[m-i-1];
                    a[m-i-1] = temp;
                }

//                for(int x: a) {
//                    pw.print(x + " ");
//                }
//                pw.println();

                int k = n-1;
                Collections.sort(al);
                for(int i=0 ; i<al.size()/2 ; i++) {
                    long temp = al.get(al.size()-1-i);
                    al.set(al.size()-1-i, al.get(i));
                    al.set(i, temp);
                }

//                for(long x: al) {
//                    pw.print(x + " ");
//                }
//                pw.println();

                int mod = 1_000_000_007;

                if(k < m) {
                    int ind = 0;
                    long prod = 1;
                    for( ; ind < (m-(k-1)) ; ind++) {
                        prod *= a[ind];
                        prod %= mod;
                    }
                    long ans = prod*(al.get(0)%mod)%mod;
                    int x = 1;
                    for( ; ind<m ; ind++, x++) {
                        ans += (al.get(x)%mod*a[ind]%mod)%mod;
                        ans %= mod;
                    }
                    ans %= mod;
                    pw.println(ans);
                }
                else if(k == m) {
                    long ans = 0;
                    for(int i=0 ; i<k ; i++) {
                        ans += al.get(i)%mod*a[i]%mod;
                        ans %= mod;
                    }
                    pw.println(ans);
                }
                else {
                    long ans = 0;
                    for(int i=0 ; i<k ; i++) {
                        if(i<m) {
                            ans += al.get(i)%mod*a[i]%mod;
                        }
                        else ans += al.get(i);
                        ans %= mod;
                    }
                    pw.println(ans);
                }




            }
        }
        finally {
            pw.flush();
            pw.close();
        }
    }

    static int dfs(int start, int par) {
        int c = 0;
        for(int x: adj[start]) {
            if(x != par) {
                int childs = dfs(x, start);
                c += childs;
                al.add((long)childs*(n-childs));
            }
        }
        c++;
        return c;
    }
    
    static class Reader {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

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

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

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