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>
using namespace std;
const int N = 1010;
const int mod = 1e9 + 7;
int na, nb;
vector<int> ga[N], gb[N];
namespace _prime {
int d[N], a[N];
void init() {
  for (int i = 2; i < N; i++) {
    if (!a[i]) d[a[i] = ++d[0]] = i;
    for (int j = 1; j <= a[i] && 1ll * d[j] * i < N; j++) a[d[j] * i] = j;
  }
}
}  // namespace _prime
int randseed;
int rk_p(int rk) { return _prime::d[rk + 1] * randseed; }
int add(int x, int y) {
  x += y;
  return x >= mod ? x - mod : x;
}
int sub(int x, int y) {
  x -= y;
  return x < 0 ? x + mod : x;
}
int mul(int x, int y) { return 1ll * x * y % mod; }
int calc(int x, int y) {
  int z = 1;
  while (y) {
    if (y & 1) z = mul(z, x);
    x = mul(x, x), y >>= 1;
  }
  return z;
}
int tot_status = 0;
pair<long long, int> status_list_all[4000];
int s_s_update[4000][4000];
map<pair<long long, int>, int> m_all;
int update(long long v, int sz) {
  if (m_all.find(make_pair(v, sz)) == m_all.end()) {
    status_list_all[++tot_status] = make_pair(v, sz);
    m_all[make_pair(v, sz)] = tot_status;
  }
  return m_all[make_pair(v, sz)];
}
int f[1001][4000];
int tmp[4000];
vector<pair<int, int> > can_merge;
int ans = 0;
vector<int> match_status;
void dfs(int x, int fa) {
  f[x][1] = 1;
  for (auto v : ga[x])
    if (v != fa) {
      dfs(v, x);
      for (auto u : can_merge)
        tmp[s_s_update[u.first][u.second]] =
            add(tmp[s_s_update[u.first][u.second]],
                mul(f[x][u.first], f[v][u.second]));
      for (int i = 1; i <= tot_status; i++)
        f[x][i] = add(tmp[i], f[x][i]), tmp[i] = 0;
    }
  int last = 0;
  for (auto u : match_status)
    if (last != u) ans = add(ans, f[x][u]), last = u;
}
pair<long long, int> dfs1(int x, int fa) {
  long long v = 1;
  int sz = 1;
  for (auto u : gb[x])
    if (u != fa) {
      auto w = dfs1(u, x);
      v = v + w.first * rk_p(w.second);
      sz += w.second;
    }
  return make_pair(v, sz);
}
map<long long, int> can;
int main() {
  _prime::init();
  srand(time(0));
  randseed = rand() % 10000 + 1;
  update(1, 1);
  scanf("%d", &na);
  for (int i = 1; i < na; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    ga[x].push_back(y);
    ga[y].push_back(x);
  }
  scanf("%d", &nb);
  for (int i = 1; i < nb; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    gb[x].push_back(y);
    gb[y].push_back(x);
  }
  for (int i = 1; i <= nb; i++) {
    auto v = dfs1(i, 0);
    can[v.first] = 1;
  }
  for (int v = 2; v <= 12; v++)
    for (int i = 1; i <= tot_status; i++)
      for (int j = 1; j <= tot_status; j++)
        if (status_list_all[i].second + status_list_all[j].second == v &&
            !(v == 12 && !can[status_list_all[i].first +
                              status_list_all[j].first *
                                  rk_p(status_list_all[j].second)])) {
          int u = update(
              status_list_all[i].first +
                  status_list_all[j].first * rk_p(status_list_all[j].second),
              status_list_all[i].second + status_list_all[j].second);
          s_s_update[i][j] = u;
          can_merge.push_back(make_pair(i, j));
        }
  for (auto u : can)
    if (u.second) match_status.push_back(update(u.first, nb));
  sort(match_status.begin(), match_status.end());
  dfs(1, 0);
  printf("%d\n", ans);
  return 0;
}