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.ByteArrayInputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;


public class D {

  public static void main(String[] args) throws Exception {
    new D().go();
  }
  static boolean LOCAL = System.getProperty("ONLINE_JUDGE") == null;



  Scanner in;
  String INPUT = "1\r\n" +
      "16\r\n" +
      "5 10\r\n" +
      "16 1\r\n" +
      "14 1\r\n" +
      "7 5\r\n" +
      "13 2\r\n" +
      "16 11\r\n" +
      "1 7\r\n" +
      "1 4\r\n" +
      "3 14\r\n" +
      "8 16\r\n" +
      "1 6\r\n" +
      "4 9\r\n" +
      "4 12\r\n" +
      "5 13\r\n" +
      "1 15\r\n" +
      "18\r\n" +
      "45893 9901 51229 15511 46559 28433 4231 30241 29837 34421 12953 6577 12143 52711 40493 89 34819 28571";


  void go() {
    if (LOCAL) {
      System.setIn(new ByteArrayInputStream(INPUT.getBytes()));
    }
    in = new Scanner(System.in);
    long startTime = System.currentTimeMillis();
    solve();
    if (LOCAL) {
      System.out.printf("[%dms]", System.currentTimeMillis()-startTime);
    }
    in.close();
  }


  PrintWriter out = new PrintWriter(System.out);
  StringBuffer sb = new StringBuffer();

  void solve() {


    int t = in.nextInt();
    for (int i=1; i<=t; i++) {
      solve2(i);
    }


    out.flush();
  } // end of solve



  List<Long> dist_index;
  int N_NODES;


  void solve2(int caseNr) {


    int n = in.nextInt();
    N_NODES = n;

    Node[] nodes = new Node[n+1];
    for (int i = 1; i <= n; i++) {
      nodes[i] = new Node(i);
    }

    for (int i=0; i<n-1; i++) {
      int edge1 = in.nextInt();
      int edge2 = in.nextInt();
      nodes[edge2].addChild(nodes[edge1]);
      nodes[edge1].addChild(nodes[edge2]);
    }

    int m = in.nextInt();
    // int[] p = new int[m];
    List<Long> primes = new ArrayList<>();
    for (int i=0; i<m; i++) {
      // p[i] = in.nextInt();
      primes.add(in.nextLong());
    }

    for (int i=m; i<n-1; i++) {
      primes.add(1l);
    }


    // if (caseNr != 3) return;


    dist_index = new ArrayList<>();

    // ZZ.showIntegerArray(p);

    //    for (int i = 1; i <= n; i++) {
    //      System.out.println(nodes[i]);
    //    }


    count(nodes[1]);

    //    Collections.sort(dist_index, Collections.reverseOrder());
    //    Collections.sort(primes, Collections.reverseOrder());
    Collections.sort(dist_index);
    Collections.sort(primes);




    long sum = 0;
    int MOD = (int) 1e9+7;

    long last_prime = primes.get(n-2);
    for (int i = n-1; i < m; i++) {
      last_prime = (last_prime * primes.get(i) % MOD) % MOD;
    }
    List<Long> primes2 = new ArrayList<>();
    for (int i = 0; i < n-2; i++) {
      primes2.add(primes.get(i));
    }
    primes2.add(last_prime);
    primes = primes2;


    // last number that gets multiplied
    // 45893
    // System.out.println(dist_index);
    // System.out.println(primes);


    for (int i = 0; i < n-1; i++) {
      // for (int i = n-2; i >= 0; i--) {
      // System.out.println(dist_index.get(i));
      // System.out.println(primes.get(i));
      long term = primes.get(i) * (dist_index.get(i) % MOD);
      term = term % MOD;
      sum = sum + term;
      sum = sum % MOD;
      // System.out.println(sum);
    }



    System.out.println(sum);



    //  10626458
    // 667739716

  } // end of solve2



  int count(Node n) {
    n.visited = true;
    List<Integer> child_count = new ArrayList<>();

    for (Node child : n.children) {
      // nr_children += count(child);
      if (!child.visited) {
        child_count.add(count(child));
      }
    }


    int nr_children_sum = 0;
    for (int count : child_count) {
      // System.out.printf("Node(%d) subtree=%d \n", n.node_index, count);
      dist_index.add((long) count * (N_NODES-count));
      nr_children_sum += count;
    }

    //    if (nr_children > 0) {
    //      System.out.printf("Node(%d) subtree=%d \n", n.node_index, nr_children);
    //    }

    return nr_children_sum + 1;
  }


  class Node {
    List<Node> children = new ArrayList<>();
    int node_index;
    boolean visited = false;

    public Node(int node_index) {
      this.node_index = node_index;
    }
    public void addChild(Node n) {
      children.add(n);
    }

    @Override
    public String toString() {
      return String.format("Node(%d) children=%d", node_index, children.size());
    }

  }



}












