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 mod = 1e9 + 7;
int n, m, id[(1 << 24) + 5], SZ;
int ans;
vector<int> G[13], E[1005];
inline int length(int s) { return 32 - __builtin_clz(s); }
inline int combine(int s, int t) { return s << length(t) | t; }
inline void inc(int& x, int y) { x = x + y < mod ? x + y : x + y - mod; }
map<int, vector<int> > _list;
vector<int> f[1005];
int search(int u, int pa) {
  int s = 1;
  vector<int> nw;
  for (int v : G[u]) {
    if (v == pa) continue;
    nw.push_back(search(v, u));
  }
  sort(nw.begin(), nw.end());
  for (int x : nw) s = combine(s, x);
  s <<= 1;
  if (!_list.count(s)) _list[s] = nw;
  return s;
}
void dfs(int u, int pa) {
  static int g[2][(1 << 12) + 5];
  static vector<int> nw;
  f[u].clear();
  f[u].resize(SZ + 1);
  for (int v : E[u]) {
    if (v == pa) continue;
    dfs(v, u);
  }
  for (map<int, vector<int> >::iterator it = _list.begin(); it != _list.end();
       ++it) {
    nw = it->second;
    int all = (1 << (int)(nw).size()) - 1;
    memset(g[0], 0, sizeof(int) * (all + 1));
    g[0][0] = 1;
    for (int v : E[u]) {
      if (v == pa) continue;
      memcpy(g[1], g[0], sizeof(int) * (all + 1));
      for (int i = (0), _ed = ((int)(nw).size() - 1); i <= _ed; ++i) {
        if (!f[v][id[nw[i]]]) continue;
        int w = f[v][id[nw[i]]];
        for (int s = (0), _ed = (all); s <= _ed; ++s)
          if (g[1][s] && (~s >> i & 1) &&
              (!i || nw[i] ^ nw[i - 1] || (s >> (i - 1) & 1)))
            inc(g[0][s | (1 << i)], 1ll * g[1][s] * w % mod);
      }
    }
    f[u][id[it->first]] = g[0][all];
    if (length(it->first) == m + m) inc(ans, g[0][all]);
  }
}
int main() {
  n = read();
  for (int i = (2), _ed = (n); i <= _ed; ++i) {
    int u = read(), v = read();
    E[u].push_back(v), E[v].push_back(u);
  }
  m = read();
  for (int i = (2), _ed = (m); i <= _ed; ++i) {
    int u = read(), v = read();
    G[u].push_back(v), G[v].push_back(u);
  }
  for (int i = (1), _ed = (m); i <= _ed; ++i) search(i, 0);
  for (map<int, vector<int> >::iterator it = _list.begin(); it != _list.end();
       ++it)
    id[it->first] = ++SZ;
  dfs(1, 0);
  printf("%d\n", ans % mod);
  return 0;
}