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;
int IN() {
  int x = 0, f = 0, ch;
  for (; (ch = getchar()) < '0' || ch > '9';) f = (ch == '-');
  for (; ch >= '0' && ch <= '9'; (ch = getchar())) x = x * 10 + ch - '0';
  return f ? -x : x;
}
int M, edge[1005][1005], son[1005][1005], idx[1005][1005];
inline void Plu(int& a, int b) {
  a += b;
  if (a >= 1000000007) a -= 1000000007;
}
struct Tree {
  int N, D, st[1005];
  int F[1005][15], G[1 << 15];
  struct Lin {
    int v, next;
  } E[1005 << 1];
  void Link(int u, int v) {
    E[++D] = (Lin){v, st[u]};
    st[u] = D;
    E[++D] = (Lin){u, st[v]};
    st[v] = D;
  }
  void Init(int kind) {
    N = IN();
    for (int i = 2, lim = N; i <= lim; i++) {
      int u = IN(), v = IN();
      Link(u, v);
      if (kind) {
        edge[u][++*edge[u]] = v;
        edge[v][++*edge[v]] = u;
      }
    }
    if (kind) M = N;
  }
  void DFS(int u, int f) {
    for (int i = st[u], v; i; i = E[i].next)
      if ((v = E[i].v) != f) DFS(v, u);
    for (int a = 1, lim = M; a <= lim; a++) {
      int U = (1 << *son[a]) - 1;
      for (int j = 0, lim = U; j <= lim; j++) G[j] = 0;
      G[0] = 1;
      for (int i = st[u], v; i; i = E[i].next)
        if ((v = E[i].v) != f) {
          for (int s = U, lim = 0; s >= lim; s--)
            if (G[s]) {
              for (int j = 1, lim = *son[a]; j <= lim; j++) {
                int b = son[a][j], t = 1 << (idx[a][b] - 1);
                if (!(t & s)) Plu(G[s | t], 1ll * G[s] * F[v][b] % 1000000007);
              }
            }
        }
      F[u][a] = G[U];
    }
  }
  int Work(int Rt) {
    for (int i = 1, lim = N; i <= lim; i++)
      for (int j = 1, lim = M; j <= lim; j++) F[i][j] = 0;
    DFS(1, 0);
    int ret = 0;
    for (int i = 1, lim = N; i <= lim; i++) Plu(ret, F[i][Rt]);
    return ret;
  }
} A, B;
int Pow(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1, a = 1ll * a * a % 1000000007)
    if (b & 1) ret = 1ll * ret * a % 1000000007;
  return ret;
}
void DFS(int u, int f) {
  for (int i = 1, lim = *edge[u]; i <= lim; i++) {
    int v = edge[u][i];
    if (v != f) {
      son[u][++*son[u]] = v;
      idx[u][v] = *son[u];
      DFS(v, u);
    }
  }
}
int main(int argc, char* argv[]) {
  A.Init(0);
  B.Init(1);
  int retA = 0, retB = 0;
  for (int i = 1, lim = M; i <= lim; i++) {
    for (int j = 0, lim = M; j <= lim; j++)
      for (int k = 0, lim = M; k <= lim; k++) son[j][k] = idx[j][k] = 0;
    DFS(i, 0);
    Plu(retA, A.Work(i));
    Plu(retB, B.Work(i));
  }
  cout << 1ll * retA * Pow(retB, 1000000007 - 2) % 1000000007 << endl;
  cerr << retA << " " << retB << endl;
  return 0;
}