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 p = 1e9 + 7, Maxn = 4105;
int n, m, maxi, cnt, tot, head[Maxn], S[13][13], f[1055][13][Maxn];
long long get_inv(long long x) {
  if (x <= 1) return 1;
  return (p - p / x) * get_inv(p % x) % p;
}
struct edg {
  int nxt, to;
} edge[2 * Maxn];
void add(int x, int y) {
  edge[++cnt] = (edg){head[x], y};
  head[x] = cnt;
}
int init_dfs(int u, int fa) {
  int sta = 1 << (u - n - 1);
  for (int i = head[u]; i; i = edge[i].nxt) {
    int to = edge[i].to;
    if (to != fa) sta |= init_dfs(to, u);
  }
  return sta;
}
void dfs(int u, int fa) {
  for (int i = 1; i <= m; i++)
    for (int j = 0; j <= maxi; j++) f[u][i][j] = 0;
  for (int i = 1; i <= m; i++) f[u][i][1 << (i - 1)] = 1;
  for (int i = head[u]; i; i = edge[i].nxt) {
    int to = edge[i].to;
    if (to != fa) {
      dfs(to, u);
      for (int s = maxi; s >= 0; s--)
        for (int j = 1; j <= m; j++)
          if (s & (1 << (j - 1)))
            for (int k = head[j + n]; k; k = edge[k].nxt)
              if (!(s & S[j][edge[k].to - n]))
                (f[u][j][s | S[j][edge[k].to - n]] +=
                 f[u][j][s] *
                 (long long)f[to][edge[k].to - n][S[j][edge[k].to - n]] % p) %=
                    p;
    }
  }
  for (int i = 1; i <= m; i++) (tot += f[u][i][maxi]) %= p;
}
int work(int root) {
  tot = 0;
  dfs(root, 0);
  return tot;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y), add(x, y), add(y, x);
  }
  scanf("%d", &m);
  for (int i = 1; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y), add(x + n, y + n), add(y + n, x + n);
  }
  maxi = (1 << m) - 1;
  for (int i = n + 1; i <= n + m; i++)
    for (int j = n + 1; j <= n + m; j++)
      if (i != j) S[i - n][j - n] = init_dfs(j, i);
  printf("%lld", work(1) * get_inv(work(n + 1)) % p);
  return 0;
}