Problem: You are given two trees (connected undirected acyclic graphs) S and T.

Count the number of subtrees (connected subgraphs) of S that are isomorphic to tree T. Since this number can get quite large, output it modulo 109 + 7.

Two subtrees of tree S are considered different, if there exists a vertex in S that belongs to exactly one of them.

Tree G is called isomorphic to tree H if there exists a bijection f from the set of vertices of G to the set of vertices of H that has the following property: if there is an edge between vertices A and B in tree G, then there must be an edge between vertices f(A) and f(B) in tree H. And vice versa — if there is an edge between vertices A and B in tree H, there must be an edge between f - 1(A) and f - 1(B) in tree G.

Input

The first line contains a single integer |S| (1 ≤ |S| ≤ 1000) — the number of vertices of tree S.

Next |S| - 1 lines contain two integers ui and vi (1 ≤ ui, vi ≤ |S|) and describe edges of tree S.

The next line contains a single integer |T| (1 ≤ |T| ≤ 12) — the number of vertices of tree T.

Next |T| - 1 lines contain two integers xi and yi (1 ≤ xi, yi ≤ |T|) and describe edges of tree T.

Output

On the first line output a single integer — the answer to the given task modulo 109 + 7.

Examples

Input

5
1 2
2 3
3 4
4 5
3
1 2
2 3


Output

3


Input

3
2 3
3 1
3
1 2
1 3


Output

1


Input

7
1 2
1 3
1 4
1 5
1 6
1 7
4
4 1
4 2
4 3


Output

20


Input

5
1 2
2 3
3 4
4 5
4
4 1
4 2
4 3


Output

0

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
template <int MOD>
struct Integral {
  int v_ = 0;
  template <typename T>
  Integral(T v) : v_(norm(v)) {
    static_assert(std::is_integral<T>::value, "input should be an integral.");
  }
  Integral() = default;
  ~Integral() = default;
  template <typename T>
  T norm(T v) const {
    if constexpr (std::is_same<long long, T>::value) {
      v %= MOD;
      if (v < 0) v += MOD;
    } else {
      if (v >= MOD) v -= MOD;
      if (v < 0) v += MOD;
      if (v >= MOD || v < 0) {
        v %= MOD;
        if (v < 0) v += MOD;
      }
    }
    return v;
  }
  int val() const { return v_; }
  Integral operator+(const Integral& rhs) const {
    return Integral(val() + rhs.val());
  }
  Integral operator-(const Integral& rhs) const {
    return Integral(val() - rhs.val());
  }
  Integral operator*(const Integral& rhs) const {
    return Integral(val() * 1LL * rhs.val());
  }
  Integral operator/(const Integral& rhs) const { return *this * rhs.inv(); }
  Integral& operator+=(const Integral& rhs) { return *this = *this + rhs; }
  Integral& operator-=(const Integral& rhs) { return *this = *this - rhs; }
  Integral& operator*=(const Integral& rhs) { return *this = *this * rhs; }
  Integral& operator/=(const Integral& rhs) { return *this = *this / rhs; }
  bool operator==(const Integral& rhs) const { return val() == rhs.val(); }
  bool operator!=(const Integral& rhs) const { return !(*this == rhs); }
  const Integral operator-() const { return Integral(-val()); }
  const Integral operator++() {
    v_ = norm(v_ + 1);
    return *this;
  }
  const Integral operator++(int) {
    Integral ret = *this;
    ++(*this);
    return ret;
  }
  const Integral operator--() {
    v_ = norm(v_ - 1);
    return *this;
  }
  const Integral operator--(int) {
    Integral ret = *this;
    --(*this);
    return ret;
  }
  Integral power(long long b) const {
    long long ret = 1 % MOD, a = v_;
    for (; b; b >>= 1, a = a * a % MOD)
      if (b & 1) ret = ret * a % MOD;
    return ret;
  }
  Integral inv() const { return power(MOD - 2); }
};
template <int MOD>
std::string to_string(const Integral<MOD>& v) {
  return std::string("Int<>{") + std::to_string(v.val()) + "}";
}
template <int MOD, bool kAllowBruteForce = false>
struct Binomial {
  std::vector<Integral<MOD>> factor, inv_factor;
  explicit Binomial(int n = 0) : factor(n + 1), inv_factor(n + 1) {
    factor[0] = 1;
    for (int i = 1; i <= n; ++i) factor[i] = factor[i - 1] * i;
    inv_factor[n] = factor[n].inv();
    for (int i = n; i >= 1; --i) inv_factor[i - 1] = inv_factor[i] * i;
  }
  ~Binomial() = default;
  template <typename T>
  Integral<MOD> operator()(T a, T b) const {
    if (a < b || b < 0) return 0;
    if (a < factor.size()) return factor[a] * inv_factor[b] * inv_factor[a - b];
    if constexpr (!kAllowBruteForce) {
      throw std::out_of_range("Binomial");
    } else {
      b = std::min(b, a - b);
      Integral<MOD> ret = 1;
      for (T i = 1; i <= b; ++i) ret = ret * (a + 1 - i) / i;
      return ret;
    }
  }
};
template <int MOD>
struct PowerTable : public std::vector<Integral<MOD>> {
  PowerTable(int n, const Integral<MOD>& g) {
    static_assert(sizeof(PowerTable) == sizeof(std::vector<Integral<MOD>>), "");
    this->resize(n + 1);
    this->at(0) = 1;
    this->at(1) = g;
    for (int i = 2; i < this->size(); ++i)
      this->at(i) = this->at(i - 1) * this->at(1);
  }
};
const int MOD = 1e9 + 7;
using Mint = Integral<MOD>;
using Binom = Binomial<MOD>;
const int kN = 2000 + 5;
const int kM = 23;
std::vector<int> edges[kN];
std::vector<int> Tedges[kM];
int n, m;
int get_centroid(int n, std::vector<int> edges[]) {
  int root = 0;
  std::vector<int> parent(n, -1);
  std::vector<int> sz(n);
  std::vector<int> que(n);
  std::vector<int> balance(n);
  int qf = 0, qe = 0;
  que[qe++] = root;
  parent[root] = -1;
  while (qf != qe) {
    int u = que[qf++];
    sz[u] = 1;
    balance[u] = 0;
    for (int v : edges[u]) {
      if (parent[u] != v) {
        parent[v] = u;
        que[qe++] = v;
      }
    }
  }
  for (int i = qe - 1; i >= 0; --i) {
    int u = que[i];
    if (i) {
      sz[parent[u]] += sz[u];
      balance[parent[u]] = std::max(balance[parent[u]], sz[u]);
    }
    balance[u] = std::max(balance[u], qe - sz[u]);
  }
  for (int i = qe - 1; i > 0; --i)
    if (balance[que[i]] < balance[root]) root = que[i];
  1145141919810;
  1145141919810;
  1145141919810;
  1145141919810;
  1145141919810;
  1145141919810;
  return root;
}
std::vector<std::vector<int>> hashes;
std::map<std::vector<int>, int> map;
int h;
int prepare_hashes(int u, int fa) {
  std::vector<int> vec;
  for (int v : Tedges[u])
    if (v != fa) {
      vec.emplace_back(prepare_hashes(v, u));
    }
  std::sort(vec.begin(), vec.end());
  if (!map.count(vec)) {
    int w = hashes.size();
    hashes.emplace_back(vec);
    map[vec] = w;
  }
  return map[vec];
}
std::vector<std::pair<int, int>> get_freq(int id) {
  std::vector<std::pair<int, int>> ret;
  for (int i = 0, j = 0; i < hashes[id].size(); i = j++) {
    while (j < hashes[id].size() && hashes[id][j] == hashes[id][i]) ++j;
    ret.emplace_back(hashes[id][i], j - i);
  }
  return ret;
}
std::vector<Mint> f[kN];
std::vector<Mint> g[kN];
std::vector<int> decode(int mask,
                        const std::vector<std::pair<int, int>>& freq) {
  std::vector<int> ret(freq.size());
  for (int i = 0; i < freq.size(); ++i) {
    ret[i] = mask % (freq[i].second + 1);
    mask /= freq[i].second + 1;
  }
  return ret;
}
int encode(const std::vector<int>& code,
           const std::vector<std::pair<int, int>>& freq) {
  int ret = 0;
  for (int i = (int)freq.size() - 1; i >= 0; --i) {
    ret = ret * (freq[i].second + 1) + code[i];
  }
  return ret;
}
void dfs(int u, int fa) {
  for (int v : edges[u])
    if (v != fa) {
      dfs(v, u);
    }
  f[u].resize(h);
  for (int i = 0; i < h; ++i) {
    std::vector<std::pair<int, int>> freq = get_freq(i);
    int e = freq.size();
    int tot = 1;
    for (auto pair : freq) tot *= (pair.second + 1);
    std::vector<Mint> ways(tot);
    ways[0] = 1;
    for (int v : edges[u])
      if (v != fa) {
        for (int mask = tot - 1; mask >= 0; --mask)
          if (ways[mask].val()) {
            std::vector<int> code = decode(mask, freq);
            for (int j = 0; j < e; ++j)
              if (code[j] < freq[j].second && f[v][freq[j].first].val()) {
                ++code[j];
                int new_mask = encode(code, freq);
                --code[j];
                ways[new_mask] += ways[mask] * f[v][freq[j].first];
              }
          }
      }
    f[u][i] = ways.back();
  }
}
void dfs1(int u, int fa, const std::vector<Mint>& up) {
  int q = edges[u].size();
  g[u].resize(h);
  std::vector<std::vector<Mint>> down(q, std::vector<Mint>(h));
  for (int i = 0; i < h; ++i) {
    std::vector<std::pair<int, int>> freq = get_freq(i);
    int e = freq.size();
    int tot = 1;
    for (auto pair : freq) tot *= (pair.second + 1);
    std::vector<Mint> ways(tot);
    ways[0] = 1;
    for (int r = q - 1; r >= 0; --r) {
      int v = edges[u][r];
      const std::vector<Mint>& coef = v == fa ? up : f[v];
      for (int mask = tot - 1; mask >= 0; --mask)
        if (ways[mask].val()) {
          std::vector<int> code = decode(mask, freq);
          for (int j = 0; j < e; ++j)
            if (code[j] < freq[j].second && coef[freq[j].first].val()) {
              ++code[j];
              int new_mask = encode(code, freq);
              --code[j];
              ways[new_mask] += ways[mask] * coef[freq[j].first];
            }
        }
    }
    g[u][i] = ways.back();
    for (int r = q - 1; r >= 0; --r) {
      int v = edges[u][r];
      if (v == fa) continue;
      const std::vector<Mint>& coef = f[v];
      std::vector<Mint> b = ways;
      for (int mask = 0; mask < tot; ++mask)
        if (b[mask].val()) {
          std::vector<int> code = decode(mask, freq);
          for (int j = 0; j < e; ++j)
            if (code[j] < freq[j].second && coef[freq[j].first].val()) {
              ++code[j];
              int new_mask = encode(code, freq);
              --code[j];
              b[new_mask] -= b[mask] * coef[freq[j].first];
            }
        }
      down[r][i] = b.back();
    }
  }
  for (int r = q - 1; r >= 0; --r) {
    int v = edges[u][r];
    if (v == fa) continue;
    dfs1(v, u, down[r]);
  }
}
int solve() {
  int centroid = get_centroid(m + m - 1, Tedges);
  prepare_hashes(centroid, -1);
  h = hashes.size();
  dfs(0, -1);
  dfs1(0, -1, std::vector<Mint>(h, 0));
  1145141919810;
  for (int u = 0; u < n + n - 1; ++u) {
    1145141919810;
  }
  Mint result = 0;
  if (centroid < m) {
    for (int u = 0; u < n; ++u) {
      result += g[u].back();
    }
  } else {
    for (int u = n; u < n + n - 1; ++u) {
      result += g[u].back();
    }
  }
  return result.val();
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::istream& reader = std::cin;
  reader >> n;
  for (int i = 0; i < n - 1; ++i) {
    int x, y;
    reader >> x >> y;
    --x;
    --y;
    edges[x].emplace_back(n + i);
    edges[n + i].emplace_back(x);
    edges[y].emplace_back(n + i);
    edges[n + i].emplace_back(y);
  }
  reader >> m;
  for (int i = 0; i < m - 1; ++i) {
    int x, y;
    reader >> x >> y;
    --x;
    --y;
    Tedges[x].emplace_back(m + i);
    Tedges[m + i].emplace_back(x);
    Tedges[y].emplace_back(m + i);
    Tedges[m + i].emplace_back(y);
  }
  printf("%d\n", solve());
}