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;
template <typename T>
void chkmax(T &x, T y) {
  x = x > y ? x : y;
}
template <typename T>
void chkmin(T &x, T y) {
  x = x < y ? x : y;
}
template <typename T>
void read(T &x) {
  x = 0;
  int f = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
  x *= f;
}
const int N = 1010, Mod = 1e9 + 7;
vector<int> e[N], E[N];
int ans, val[N];
unordered_map<int, vector<int> > h;
unordered_map<int, int> vis, g[N];
int len(int x) { return 32 - __builtin_clz(x); }
int dfs(int x, int fa) {
  val[x] = 1;
  vector<int> cur;
  for (int y : E[x])
    if (y != fa) cur.emplace_back(dfs(y, x));
  sort(cur.begin(), cur.end());
  for (int v : cur) val[x] = val[x] << len(v) | v;
  val[x] <<= 1;
  if (!h.count(val[x])) h[val[x]] = cur;
  return val[x];
}
void DFS(int x, int fa) {
  for (int y : e[x])
    if (y != fa) DFS(y, x);
  for (auto p : h) {
    auto &v = p.second;
    int val = p.first, n = v.size(), msk = (1 << n) - 1;
    static int f[2][1 << 12];
    for (int i = 0; i <= msk; i++) f[0][i] = f[1][i] = 0;
    int las = 0;
    f[0][0] = 1;
    for (int y : e[x]) {
      if (y == fa) continue;
      int now = las ^ 1;
      for (int i = 0; i <= msk; i++) f[now][i] = f[las][i];
      for (int i = 0; i < n; i++) {
        if (!g[y][v[i]]) continue;
        int t = g[y][v[i]];
        for (int j = 0; j <= msk; j++) {
          if (!f[las][j] || ((j >> i) & 1)) continue;
          if (!i || v[i] != v[i - 1] || ((j >> i - 1) & 1) == 0)
            (f[now][j ^ (1 << i)] += 1ll * f[las][j] * t % Mod) %= Mod;
        }
      }
      las = now;
    }
    (g[x][val] += f[las][msk]) %= Mod;
    if (vis[val]) (ans += f[las][msk]) %= Mod;
  }
}
int main() {
  int n, m;
  read(n);
  for (int i = 1; i < n; i++) {
    int x, y;
    read(x), read(y);
    e[x].emplace_back(y), e[y].emplace_back(x);
  }
  read(m);
  for (int i = 1; i < m; i++) {
    int x, y;
    read(x), read(y);
    E[x].emplace_back(y), E[y].emplace_back(x);
  }
  for (int i = 1; i <= m; i++) vis[dfs(i, 0)] = 1;
  DFS(1, 0);
  cout << ans << '\n';
  return 0;
}