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;
inline int read() {
  char ch = getchar();
  int x = 0, op = 0;
  while (!isdigit(ch)) op |= (ch == '-'), ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return op ? -x : x;
}
const int N = 2005, M = 15;
const int mod = 1e9 + 7;
int fac[N], f[N][M], flag[M], pre[M][M][M];
vector<int> e[N], E[M], s[M][M];
int n, m, x, y, rev;
int Ha[M][M];
int calc(int u, int fa, int rt) {
  int res = 1, sum = 19260817, tmp;
  for (auto v : E[u])
    if (v != fa) {
      tmp = calc(v, u, rt);
      res = 1ll * res * tmp % mod;
      sum = (sum + tmp) % mod;
    }
  res = 1ll * res * sum % mod;
  return Ha[rt][u] = res;
}
void doit(int u, int fa, int rt) {
  for (auto v : E[u])
    if (v != fa) {
      doit(v, u, rt);
      s[rt][u].push_back(v);
    }
  int sz = s[rt][u].size();
  for (int i = (0); i < (sz); i++) {
    for (int j = (0); j <= (i - 1); j++)
      if (Ha[rt][s[rt][u][i]] == Ha[rt][s[rt][u][j]]) pre[rt][u][i] |= (1 << j);
  }
}
void init() {
  for (int i = (1); i <= (m); i++) {
    calc(i, 0, i);
    for (int j = (1); j <= (i - 1); j++)
      if (Ha[i][i] == Ha[j][j]) {
        flag[i] = 1;
        break;
      }
    if (flag[i]) continue;
    doit(i, 0, i);
  }
}
inline void upd(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
int g[1 << M], h[1 << M], rt, res;
void dfs(int u, int fa) {
  vector<int> c;
  for (auto v : e[u])
    if (v != fa) dfs(v, u), c.push_back(v);
  int cc = c.size();
  for (int i = (1); i <= (m); i++) {
    int sz = s[rt][i].size();
    if (sz > cc) {
      f[u][i] = 0;
      continue;
    }
    for (int st = (0); st < ((1 << sz)); st++) g[st] = 0;
    g[0] = 1;
    for (int k = (0); k < (cc); k++) {
      for (int st = (0); st < ((1 << sz)); st++) h[st] = g[st];
      for (int st = (0); st < ((1 << sz)); st++)
        if (g[st])
          for (int j = (0); j < (sz); j++)
            if (!(st >> j & 1) && f[c[k]][s[rt][i][j]] &&
                ((st & pre[rt][i][j]) == pre[rt][i][j]))
              upd(h[st | (1 << j)], 1ll * g[st] * f[c[k]][s[rt][i][j]] % mod);
      for (int st = (0); st < ((1 << sz)); st++) g[st] = h[st];
    }
    f[u][i] = g[(1 << sz) - 1];
  }
  res = (res + f[u][rt]) % mod;
}
int solve(int k) {
  rt = k, res = 0;
  dfs(1, 0);
  return res;
}
int main() {
  scanf("%d", &n);
  for (int i = (1); i <= (n - 1); i++) {
    scanf("%d%d", &x, &y);
    e[x].push_back(y), e[y].push_back(x);
  }
  scanf("%d", &m);
  for (int i = (1); i <= (m - 1); i++) {
    scanf("%d%d", &x, &y);
    E[x].push_back(y), E[y].push_back(x);
  }
  init();
  int ans = 0;
  for (int i = (1); i <= (m); i++)
    if (!flag[i]) ans = (ans + solve(i)) % mod;
  printf("%d\n", ans);
  return 0;
}