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;
const int oo = 2139063143;
const int N = 1010, M = 1 << 12 | 1;
const int P = 1000000007;
const double eps = 1e-7;
template <typename T>
inline void sc(T &x) {
  x = 0;
  static int p;
  p = 1;
  static char c;
  c = getchar();
  while (!isdigit(c)) {
    if (c == '-') p = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c - 48);
    c = getchar();
  }
  x *= p;
}
template <typename T>
inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
inline void pr(T x) {
  print(x), putchar('\n');
}
template <typename T1, typename T2>
void chkmax(T1 &A, T2 B) {
  A = A >= B ? A : B;
}
template <typename T1, typename T2>
void chkmin(T1 &A, T2 B) {
  A = A <= B ? A : B;
}
int del(int x) { return x >= P ? x - P : x; }
void add(int &x, int y) { x = del(x + y); }
int n, m, jc[N], inv[N];
void init() {
  inv[0] = inv[1] = 1;
  for (int i = 2; i <= n; i++) inv[i] = (long long)(P - P / i) * inv[P % i] % P;
  for (int i = 2; i <= n; i++) inv[i] = (long long)inv[i] * inv[i - 1] % P;
}
vector<int> A[N], B[N];
unsigned long long h[N];
int st[15][15], z[15], siz[15];
void geth(int u, int fa) {
  siz[u] = 1;
  vector<unsigned long long> f;
  z[u] = 0;
  for (int v : B[u])
    if (v != fa)
      geth(v, u), f.push_back(h[v]), st[u][++z[u]] = v, siz[u] += siz[v];
  sort(f.begin(), f.end());
  h[u] = siz[u];
  for (unsigned long long x : f) h[u] = h[u] * 233 + x;
}
map<unsigned long long, int> p1, p2;
int f[N][M], g[M], ans = 0;
void dfs(int u, int fa) {
  for (int v : A[u])
    if (v != fa) dfs(v, u);
  for (int x = 1; x <= m; x++) {
    if ((int)A[u].size() - (fa > 0) < z[x]) {
      f[u][x] = 0;
      continue;
    }
    for (int i = 1; i <= z[x]; i++) ++p2[h[st[x][i]]];
    memset(g, 0, sizeof(g));
    g[0] = 1;
    int S = (1 << z[x]) - 1;
    for (int v : A[u])
      if (v != fa) {
        for (int s = S; s >= 0; s--)
          if (g[s])
            for (int i = 1; i <= z[x]; i++)
              if (!(s >> (i - 1) & 1))
                if (f[v][st[x][i]])
                  add(g[s | 1 << (i - 1)],
                      (long long)g[s] * f[v][st[x][i]] % P);
      }
    f[u][x] = g[S];
    for (int i = 1; i <= z[x]; i++)
      if (p2[h[st[x][i]]])
        f[u][x] = (long long)f[u][x] * inv[p2[h[st[x][i]]]] % P,
        p2[h[st[x][i]]] = 0;
  }
}
int main() {
  sc(n);
  init();
  for (int i = 1; i < n; i++) {
    int x, y;
    sc(x), sc(y);
    A[x].push_back(y), A[y].push_back(x);
  }
  sc(m);
  for (int i = 1; i < m; i++) {
    int x, y;
    sc(x), sc(y);
    B[x].push_back(y), B[y].push_back(x);
  }
  for (int rt = 1; rt <= m; rt++) {
    geth(rt, 0);
    if (p1[h[rt]]) continue;
    p1[h[rt]] = 1;
    dfs(1, 0);
    for (int u = 1; u <= n; u++) add(ans, f[u][rt]);
  }
  pr(ans);
  return 0;
}