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() {
  register int x = 0, f = 1;
  register char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = 0;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + (ch ^ '0');
    ch = getchar();
  }
  return f ? x : -x;
}
const int N = 1e3 + 10, M = 15, mod = 1e9 + 7;
int n, m, num1, num2, head1[N], head2[M], ans;
map<int, vector<int> > _list;
map<int, int> f[N];
struct edge {
  int to, next;
} e1[N << 1], e2[M << 1];
inline void add1(int u, int v) {
  e1[++num1] = (edge){v, head1[u]}, head1[u] = num1;
}
inline void add2(int u, int v) {
  e2[++num2] = (edge){v, head2[u]}, head2[u] = num2;
}
inline void pls(int &x, int y) { x = x + y >= mod ? x + y - mod : x + y; }
inline int length(int x) { return 32 - __builtin_clz(x); }
inline void combine(int &x, int y) { x = x << length(y) | y; }
inline int Cal(int u, int pa) {
  int s = 1;
  vector<int> nw;
  for (int i = head2[u]; i; i = e2[i].next) {
    if (e2[i].to == pa) continue;
    nw.push_back((Cal(e2[i].to, u)));
  }
  sort(nw.begin(), nw.end());
  for (int i = (0), ed = (nw.size() - 1); i <= ed; ++i) combine(s, nw[i]);
  s <<= 1;
  if (!_list.count(s)) _list[s] = nw;
  return s;
}
inline void Dfs(int u, int pa) {
  static int g[2][1 << M];
  vector<int> son;
  for (int i = head1[u]; i; i = e1[i].next) {
    if (e1[i].to == pa) continue;
    son.push_back((e1[i].to));
    Dfs(e1[i].to, u);
  }
  for (map<int, vector<int> >::iterator it = _list.begin(); it != _list.end();
       ++it) {
    vector<int> nw = (*it).second;
    int s = (*it).first, siz = nw.size(), all = (1 << siz) - 1;
    memset(g[0], 0, sizeof(g[0]));
    g[0][0] = 1;
    for (int i = (0), ed = (son.size() - 1); i <= ed; ++i) {
      memcpy(g[1], g[0], sizeof(g[0]));
      for (int j = 0; j < siz; ++j) {
        int val = f[son[i]][nw[j]];
        if (!val) continue;
        for (int k = all; ~k; --k)
          if (g[0][k] && !((k >> j) & 1) &&
              (!j || nw[j] ^ nw[j - 1] || (k >> (j - 1)) & 1))
            pls(g[1][k | (1 << j)], 1ll * g[0][k] * val % mod);
      }
      memcpy(g[0], g[1], sizeof(g[1]));
    }
    if (g[0][all]) {
      f[u][s] = g[0][all];
      if (length(s) == m + m) pls(ans, g[0][all]);
    }
  }
}
int main() {
  n = read();
  for (int i = (2), ed = (n); i <= ed; ++i) {
    int u = read(), v = read();
    add1(u, v), add1(v, u);
  }
  m = read();
  for (int i = (2), ed = (m); i <= ed; ++i) {
    int u = read(), v = read();
    add2(u, v), add2(v, u);
  }
  for (int i = (1), ed = (m); i <= ed; ++i) Cal(i, 0);
  Dfs(1, 0);
  printf("%d\n", ans);
  return 0;
}