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.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

public class T4 {

    static class Edge implements Comparable<Edge> {

        long a = -1, b = -1;
        long w = 0L;
        boolean visited = false;
        Edge mirror;

        public Edge(long n1, long n2) {
            a = n1;
            b = n2;
        }

        @Override
        public int compareTo(Edge o) {
            return Long.compare(a,o.a);
        }

        public int compareByW(Edge o) {
            return -Long.compare(w, o.w);
        }
    }

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int t = Integer.parseInt(br.readLine());
            for (int t_ = 0; t_ < t; t_++) {
                int nodes_n = Integer.parseInt(br.readLine());
                Edge[] edges = new Edge[nodes_n*2-2];
                for (int i = 0; i < nodes_n-1; i++) {
                    String[] n1n2 = br.readLine().split(" ");
                    int n1 = Integer.parseInt(n1n2[0])-1;
                    int n2 = Integer.parseInt(n1n2[1])-1;
                    edges[i] = new Edge(n1,n2);
                    edges[i+nodes_n-1] = new Edge(n2,n1);
                    edges[i].mirror = edges[i+nodes_n-1];
                    edges[i+nodes_n-1].mirror = edges[i];
                }

                int m = Integer.parseInt(br.readLine());
                List<Long> primes = Arrays.stream(br.readLine().split(" ")).map(Long::parseLong).sorted().collect(Collectors.toList());
                solve(edges, primes);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private static void solve(Edge[] edges, List<Long> primes) {
        Arrays.sort(edges);
        whereNodeStarts = new HashMap<>();
        int lastNode = -1;
        int lastStart = -1;
        for (int i = 0; i < edges.length; i++) {
            if (edges[i].a > lastNode) {
                whereNodeStarts.put((long)lastNode, new int[]{lastStart, i});
                lastNode = (int)edges[i].a;
                lastStart = i;
            }
        }
        whereNodeStarts.put(edges[edges.length-1].a, new int[]{lastStart, edges.length});
        for (int i = 0; i < edges.length/2; i++) {
            dfs(edges, i);
        }
        List<Edge> edgesList = Arrays.stream(edges).sorted(Edge::compareByW).filter(e->e.w>0).collect(Collectors.toList());
        primes = primes.stream().sorted((a,b)->-a.compareTo(b)).collect(Collectors.toList());
        long result = 0;
        if (primes.size() > edgesList.size()) {
            long firstNum = 1;
            for (int i = 0; i < primes.size()-edgesList.size()+1; i++) {
                firstNum = (firstNum * primes.get(i)) % 1_000_000_007L;
            }
            result = edgesList.get(0).w * firstNum % 1_000_000_007L;
            for (int i = 1; i < edgesList.size(); i++) {
                result = (result + edgesList.get(i).w * primes.get(primes.size() - edgesList.size()+i)) % 1_000_000_007L;
            }
        } else {
            for (int i = 0; i < primes.size(); i++) {
                result = (result + edgesList.get(i).w * primes.get(i)) % 1_000_000_007L;
            }
            for (int i = primes.size(); i < edgesList.size(); i++) {
                result = (result + edgesList.get(i).w) % 1_000_000_007L;
            }
        }
        boolean s = true;
        System.out.println(result);
    }

    static Map<Long, int[]> whereNodeStarts;

    private static long dfs(Edge[] edges, int start) {
        if (edges[start].visited) {
            return 0;
        }
//        System.out.printf("in edge %d %d\n", edges[start].a+1, edges[start].b+1);
        edges[start].visited = true;
        edges[start].mirror.visited = true;
        int[] node_b_start_stop = whereNodeStarts.get(edges[start].b);
        int count = 1;
        for (int i = node_b_start_stop[0]; i < node_b_start_stop[1]; i++) {
            count += dfs(edges, i);
        }
        edges[start].w = count * ((long)(edges.length/2+1)-count);
//        System.out.printf("finishing edge %d %d with count %d and w %d\n", edges[start].a+1, edges[start].b+1, count, edges[start].w);
        return count;
    }

}