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.
#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + "," +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug() { cerr << endl; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug(T...);
}
struct Fast_power {
  long long integer(long long n, long long e,
                    long long my_mod = 9223372036854775807LL) {
    long long ans = 1;
    while (e) {
      if (e & 1)
        ans = (ans * n) % my_mod, e--;
      else
        n = (n * n) % my_mod, e >>= 1;
    }
    return ans;
  }
  vector<vector<long long>> matrix_multiply(vector<vector<long long>> a,
                                            vector<vector<long long>> b) {
    vector<vector<long long>> c(a.size(), vector<long long>(b[0].size(), 0));
    for (int i = 0; i < a.size(); i++)
      for (int q = 0; q < b[0].size(); q++) {
        long long num = 0;
        for (int e = 0; e < a[0].size(); i++) num += a[i][e] * b[e][q];
        c[i][q] = num;
      }
    return c;
  }
};
struct Euclidean {
  int gcdi(int a, int b) { return b ? gcdi(b, a % b) : a; }
  double gcdf(double a, double b, double accuracy) {
    return b <= accuracy ? a : gcdf(b, fmod(a, b), accuracy);
  }
};
const int maxnD = 100000 + 5;
const long long INFD = 0x3f3f3f3f;
;
struct Dijkstra {
  struct Edge {
    int from, to;
    long long dist;
  };
  struct HeapNode {
    long long d;
    int u;
    bool operator<(const HeapNode &rhs) const { return d > rhs.d; }
  };
  vector<Edge> edges;
  vector<int> G[maxnD];
  bool done[maxnD];
  long long d[maxnD];
  int p[maxnD], n;
  void init(int n) {
    this->n = n;
    for (int i = 0; i <= n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, long long dist) {
    edges.push_back((Edge){from, to, dist});
    int m = edges.size();
    G[from].push_back(m - 1);
  }
  void dijkstra(int s) {
    priority_queue<HeapNode> q;
    memset(d, INFD, sizeof(d));
    d[s] = 0;
    memset(done, 0, sizeof(done));
    q.push((HeapNode){0, s});
    while (!q.empty()) {
      HeapNode x = q.top();
      q.pop();
      int u = x.u;
      if (done[u]) continue;
      done[u] = true;
      for (int i = 0; i < G[u].size(); i++) {
        Edge &e = edges[G[u][i]];
        if (d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          q.push((HeapNode){d[e.to], e.to});
        }
      }
    }
  }
};
const int maxnL = 500000 + 5;
const int INFL = 0x3f3f3f3f;
struct LIS {
  int g[maxnL], a[maxnL], d[maxnL];
  void lis(int n) {
    for (int i = 1; i <= n; i++) g[i] = INFL;
    for (int i = 1; i < n; i++) {
      int k = lower_bound(g + 1, g + n + 1, a[i]) - g;
      g[k] = a[i];
    }
  }
};
const int maxnS = 200000 + 5;
struct SegmentTree {
  int a[maxnS];
  int sumv[maxnS * 4], minv[maxnS * 4], maxv[maxnS * 4], addv[maxnS * 4],
      setv[maxnS * 4];
  int lc, rc, v;
  int _min, _max, _sum;
  void build(int l, int r, int o) {
    if (l == r) return void(sumv[o] = minv[o] = maxv[o] = a[l]);
    build(l, (l + r) >> 1, o << 1);
    build(((l + r) >> 1) + 1, r, o << 1 | 1);
  }
  void maintain(int l, int r, int o) {
    sumv[o] = minv[o] = maxv[o] = a[l];
    if (r > l) {
      sumv[o] = sumv[o << 1] + sumv[o << 1 | 1];
      minv[o] = min(minv[o << 1], minv[o << 1 | 1]);
      maxv[o] = max(maxv[o << 1], maxv[o << 1 | 1]);
    }
    minv[o] += addv[o], maxv[o] += addv[o], sumv[o] += addv[o] * (r - l + 1);
  }
  void update(int l, int r, int o) {
    if (l >= lc && r <= rc)
      addv[o] += v;
    else {
      int m = (l + r) >> 1;
      if (lc <= m) update(l, (l + r) >> 1, o << 1);
      if (rc > m) update(((l + r) >> 1) + 1, r, o << 1 | 1);
    }
    maintain(l, r, o);
  }
  void query(int l, int r, int o, int add) {
    if (lc <= l && r <= rc) {
      _sum += sumv[o] + add * (r - l + 1);
      _min = min(_min, minv[o] + add);
      _max = max(_max, maxv[o] + add);
    } else {
      int m = (l + r) >> 1;
      if (lc <= m) query(l, m, o << 1, add + addv[o]);
      if (rc > m) query(m + 1, r, o << 1 | 1, add + addv[o]);
    }
  }
};
const int maxnB = 100000 + 5;
struct BIT {
  int c[maxnB], n;
  int lowbit(int x) { return x & -x; }
  int sum(int x) {
    int ret = 0;
    while (x > 0) {
      ret += c[x];
      x -= lowbit(x);
    }
    return ret;
  }
  void add(int x, int d) {
    while (x <= n) {
      c[x] += d;
      x += lowbit(x);
    }
  }
};
const int INF = 0x3f3f3f3f;
const int maxn = 100000 + 5;
const long long mod = 1000000000 + 7;
long long a[maxn], n;
vector<int> G[maxn];
vector<long long> ans;
long long dfs(int u, int fa) {
  long long num = 1;
  for (int i = 0; i < G[u].size(); i++)
    if (G[u][i] != fa) num += dfs(G[u][i], u);
  if (fa != -1) ans.push_back((n - num) * num);
  return num;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    cin >> n;
    for (int i = 1; i <= n; i++) G[i].clear();
    ans.clear();
    int f1, f2;
    for (int i = 0; i < n - 1; i++)
      cin >> f1 >> f2, G[f1].push_back(f2), G[f2].push_back(f1);
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) cin >> a[i];
    if (m < n - 1)
      for (int i = m; i < n - 1; i++) a[i] = 1;
    sort(a, a + max((long long)m, n - 1));
    int pos;
    for (int i = 1; i <= n; i++)
      if (G[i].size() == 1) {
        pos = i;
        break;
      }
    dfs(pos, -1);
    sort(ans.begin(), ans.end());
    long long sum = 0, sum2 = ans[n - 2];
    for (int i = n - 2; i < max(n - 1, (long long)m); i++)
      sum2 = (sum2 * a[i]) % mod;
    for (int i = 0; i < n - 2; i++) sum = (sum + a[i] * ans[i] % mod) % mod;
    sum = (sum + sum2) % mod;
    cout << sum << endl;
  }
  return 0;
}
