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>
const int p = 1000000007;
int c[12][15], e[12][15], g[12][5000], h[12][5000];
int edge1[3000], next1[3000], first1[3000], deg1[3000], sum_edge1;
int edge2[30], next2[30], first2[30], deg2[30], sum_edge2;
int i, n1, n2, r, s, t, x, y;
inline int power(int x, int y) {
  int s = 1;
  for (int i = 30; i >= 0; i--) {
    s = 1LL * s * s % p;
    if (y & (1 << i)) s = 1LL * s * x % p;
  }
  return s;
}
inline void addedge1(int x, int y) {
  sum_edge1++, edge1[sum_edge1] = y, next1[sum_edge1] = first1[x],
               first1[x] = sum_edge1, deg1[x]++;
  return;
}
inline void addedge2(int x, int y) {
  sum_edge2++, edge2[sum_edge2] = y, next2[sum_edge2] = first2[x],
               first2[x] = sum_edge2, deg2[x]++;
  return;
}
inline int dfs1(int d, int x, int fx, int y, int fy) {
  if (deg1[x] < deg2[y]) return 0;
  int l = 0;
  for (int j = 1; j <= n2; j++) e[d][j] = 0;
  for (int j = first2[y]; j != 0; j = next2[j])
    if (edge2[j] != fy) l++, e[d][edge2[j]] = l;
  for (int i = 0; i < (1 << l); i++) g[d][i] = 0;
  g[d][0] = 1;
  for (int i = first1[x]; i != 0; i = next1[i])
    if (edge1[i] != fx) {
      for (int j = 0; j < (1 << l); j++) h[d][j] = g[d][j];
      for (int j = first2[y]; j != 0; j = next2[j])
        if (edge2[j] != fy)
          c[d][e[d][edge2[j]]] = dfs1(d + 1, edge1[i], x, edge2[j], y);
      for (int k = 1; k <= l; k++)
        if (c[d][k])
          for (int j = 0; j < (1 << l); j++)
            if (!(j & (1 << (k - 1))))
              g[d][j | (1 << (k - 1))] =
                  (g[d][j | (1 << (k - 1))] + 1LL * h[d][j] * c[d][k]) % p;
    }
  return g[d][(1 << l) - 1];
}
inline int dfs2(int d, int x, int fx, int y, int fy) {
  if (deg2[x] < deg2[y]) return 0;
  int l = 0;
  for (int j = 1; j <= n2; j++) e[d][j] = 0;
  for (int j = first2[y]; j != 0; j = next2[j])
    if (edge2[j] != fy) l++, e[d][edge2[j]] = l;
  for (int i = 0; i < (1 << l); i++) g[d][i] = 0;
  g[d][0] = 1;
  for (int i = first2[x]; i != 0; i = next2[i])
    if (edge2[i] != fx) {
      for (int j = 0; j < (1 << l); j++) h[d][j] = g[d][j];
      for (int j = first2[y]; j != 0; j = next2[j])
        if (edge2[j] != fy)
          c[d][e[d][edge2[j]]] = dfs2(d + 1, edge2[i], x, edge2[j], y);
      for (int k = 1; k <= l; k++)
        if (c[d][k])
          for (int j = 0; j < (1 << l); j++)
            if (!(j & (1 << (k - 1))))
              g[d][j | (1 << (k - 1))] =
                  (g[d][j | (1 << (k - 1))] + 1LL * h[d][j] * c[d][k]) % p;
    }
  return g[d][(1 << l) - 1];
}
inline void input() {
  scanf("%d", &n1);
  for (i = 1; i < n1; i++) {
    scanf("%d%d", &x, &y);
    addedge1(x, y), addedge1(y, x);
  }
  scanf("%d", &n2);
  for (i = 1; i < n2; i++) {
    scanf("%d%d", &x, &y);
    addedge2(x, y), addedge2(y, x);
  }
  for (i = 1; i <= n2; i++)
    if (deg2[i] > deg2[r]) r = i;
  return;
}
int main() {
  input();
  for (i = 1; i <= n1; i++) s = (s + dfs1(0, i, 0, r, 0)) % p;
  for (i = 1; i <= n2; i++) t = t + dfs2(0, i, 0, r, 0);
  printf("%d", 1LL * s * power(t, p - 2) % p);
  return 0;
}