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(int f = 1, int x = 0, char ch = ' ') {
  while (!isdigit(ch = getchar()))
    if (ch == '-') f = -1;
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return f * x;
}
const int N = 1e3 + 5, M = 13, S = 1 << 12 | 5, P = 1e9 + 7;
struct Edge {
  int next, to;
  Edge(int next = 0, int to = 0) : next(next), to(to){};
} edge[(N + M) << 1];
int tot, hs[N], ht[N];
void _add(int *head, int x, int y) {
  edge[++tot] = Edge(head[x], y), head[x] = tot;
}
void add(int *head, int x, int y) { _add(head, x, y), _add(head, y, x); }
int n, m, e[M], lg2[S], f[N][M][S], g[M][S], ans, res;
long long inv(int i) { return i == 1 ? 1 : P - (P / i) * inv(P % i) % P; }
void dfs(int x, int fa, int &ans, int *head) {
  for (int i = 0; i < m; ++i) f[x][i][1 << i] = 1;
  for (int i = head[x]; i; i = edge[i].next) {
    int y = edge[i].to;
    if (y == fa) continue;
    dfs(y, x, ans, head);
    for (int p = 0; p < m; ++p)
      for (int s = 0; s < 1 << m; ++s) g[p][s] = f[x][p][s];
    for (int p = 0, a = (1 << m) - 1; p < m; ++p)
      for (int s = 1; s < a; ++s)
        if (f[y][p][s])
          for (int u = e[p]; u; u -= u & -u) {
            int q = lg2[u & -u];
            for (int t = s ^ a, o = s ^ a; t; t = (t - 1) & o)
              f[x][q][s | t] =
                  (f[x][q][s | t] + 1ll * g[q][t] * f[y][p][s] % P) % P;
          }
  }
  for (int i = 0; i < m; ++i) ans = (ans + f[x][i][(1 << m) - 1]) % P;
}
int main() {
  lg2[0] = -1, n = read();
  for (int i = 1; i < n; ++i) {
    int x = read(), y = read();
    add(hs, x, y);
  }
  m = read();
  for (int i = 1; i < m; ++i) {
    int x = read() - 1, y = read() - 1;
    e[x] |= 1 << y, e[y] |= 1 << x, add(ht, x + 1, y + 1);
  }
  for (int i = 1; i < 1 << m; ++i) lg2[i] = lg2[i >> 1] + 1;
  dfs(1, 0, ans, hs), memset(f, 0, sizeof(f)), dfs(1, 0, res, ht);
  printf("%lld\n", ans * inv(res) % P);
  return 0;
}