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;
long long read() {
  long long a = 0, b = getchar(), c = 1;
  while (!isdigit(b)) c = b == '-' ? -1 : 1, b = getchar();
  while (isdigit(b)) a = a * 10 + b - '0', b = getchar();
  return a * c;
}
const int mod = 1e9 + 7;
struct edge {
  int to;
  edge *next;
};
struct node {
  int n, d[1005][1005], a[1005], b[1005];
  edge *ab, E[2005], *c[1005];
  void gao(int u, int v) {
    *ab = (edge){v, c[u]};
    c[u] = ab++;
  }
  void red() {
    n = read(), ab = E;
    if (n > 500) {
      for (int i = 1; i; i++) int x = 0;
    }
    for (int i = 1; i < n; i++) {
      int x = read(), y = read();
      gao(x, y), gao(y, x);
    }
  }
  void dfs(int i, int f) {
    int x = b[i] = 0;
    for (edge *e = c[i]; e; e = e->next)
      if (e->to != f) {
        dfs(d[i][x++] = e->to, i);
        b[i] |= 1 << e->to - 1;
      }
    a[i] = x;
  }
} a, b;
int ans, ans2, f[1005][1 << 12];
int dfs(int i, int j, int x) {
  if (!j) return !x;
  int &res = f[a.d[i][j - 1]][x];
  if (res) return res - 1;
  res = dfs(i, j - 1, x);
  for (int c = a.d[i][j - 1], k = 0; k < b.n; k++)
    if (x >> k & 1)
      res = (res +
             1ll * dfs(i, j - 1, x - (1 << k)) * dfs(c, a.a[c], b.b[k + 1])) %
            mod;
  return res++;
}
long long gao(int a, int p) {
  if (a == 1) return 1;
  return (1 + p * (a - gao(p % a, a))) / a % p;
}
int main() {
  a.red(), b.red();
  a.dfs(1, 0);
  for (int r = 1; r <= b.n; r++) {
    b.dfs(r, 0);
    for (int i = 1; i <= a.n; i++) ans = (ans + dfs(i, a.a[i], b.b[r])) % mod;
    memset(f, 0, sizeof(f));
  }
  a = b, a.dfs(1, 0);
  for (int r = 1; r <= b.n; r++) {
    b.dfs(r, 0);
    ans2 = (ans2 + dfs(1, a.a[1], b.b[r])) % mod;
    memset(f, 0, sizeof f);
  }
  ans = ans * gao(ans2, mod) % mod;
  printf("%d", ans);
  return 0;
}