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.util.*; 
public class D_665{
public static void main(String[] args)
{
   Scanner omkar = new Scanner(System.in);
   int cases = omkar.nextInt();
   for(int i = 0; i < cases; i++)
   {
      solve(omkar);
   }  
        }
public static void solve(Scanner omkar)
{
   int n = omkar.nextInt();
   Node[] arr = new Node[n];
   for(int i = 0; i < n; i++)
   {
      arr[i] = new Node();
   }
   int g, h;
   Pair[] edges = new Pair[n-1];
   for(int i = 0; i < n-1; i++)
   {
      g = omkar.nextInt()-1;
      h = omkar.nextInt()-1;
      arr[g].add(arr[h]);
      arr[h].add(arr[g]);
      edges[i] = new Pair(g, h);
   }
   Stack<Node> stack = new Stack<Node>();
   stack.push(arr[0]);
   Node x, y;
   while(!stack.empty())
   {
      x = stack.pop();
      for(int i = 0; i < x.children.size(); i++)
      {
         y = x.children.get(i);
         y.remove(x);
         y.depth = x.depth - 1;
         stack.push(y);
      }
   }
   Pair[] depths = new Pair[n];
   for(int i = 0; i < n; i++)
   {
      depths[i] = new Pair(arr[i].depth, i);
   }
   Arrays.sort(depths);
   int num;
   for(int i = 0; i < n; i++)
   {
      x = arr[depths[i].b];
      num = 1;
      for(int j = 0; j < x.children.size(); j++)
      {
         num += x.children.get(j).size;
      }
      x.size = num;
   }
   int[] sizes = new int[n-1];
   for(int i = 0; i < n-1; i++)
   {
      g = edges[i].a;
      h = edges[i].b;
      if(arr[g].depth > arr[h].depth)
      {
         sizes[i] = Math.abs(n-2*arr[h].size);
      }
      else
      {
         sizes[i] = Math.abs(n-2*arr[g].size);
      }
   }
   Arrays.sort(sizes);
   int m = omkar.nextInt();
   int[] primes = new int[m];
   for(int i = 0; i < m; i++)
   {
      primes[i] = omkar.nextInt();
   }
   Arrays.sort(primes);
   long ret = 0;
   long t;
   while(m > (n-1))
   {
      t = ((long)(primes[m-2])*(long)(primes[m-1])) % (1000000007);
      primes[m-2] = (int)(t);
      m--;
   }
   for(int i = 0; i < Math.min(m, n-1); i++)
   {
      t = ((long)((n-sizes[i])/2)*(long)((n+sizes[i])/2));
      t = t % (1000000007);
      t = t*primes[m-1-i];
      t = t % (1000000007);
      ret += t;
      ret = ret % (1000000007);
   }
   for(int i = Math.min(m, n-1); i < n-1; i++)
   {
      t = ((long)((n-sizes[i])/2)*(long)((n+sizes[i])/2));
      t = t % (1000000007);
      ret += t;
      ret = ret % (1000000007);
   }
   System.out.println(ret);
}
static class Node
{
   public ArrayList<Node> children;
   public int depth;
   public int size;
   public Node()
   {
      depth = 0;
      size = 0;
      children = new ArrayList<Node>();
   }
   public void add(Node node)
   {
      children.add(node);
   }
   public void remove(Node node)
   {
      children.remove(node);
   }
}
static class Pair implements Comparable<Pair> {
final int a;
final int b;
Pair(int a, int b) {
this.a = a;
this.b = b;
}
@Override
public int compareTo(Pair other) {
if (a != other.a) {
return (a - other.a);
} else {
return (b - other.b);
}}}

}