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 N = 1002, M = 13, P = 1e9 + 7;
int n, m, g[M][M], f[N + M][M][1 << M - 1], res, ans;
vector<int> G[N + M];
int inv(int x) { return x == 1 ? x : 1LL * (P - P / x) * inv(P % x) % P; }
int dfs(int u, int fa) {
  int sta = 1 << (u - n - 1);
  for (int v : G[u])
    if (v != fa) sta |= dfs(v, u);
  return sta;
}
void dp(int u, int fa) {
  memset(f[u], 0, sizeof(f[u]));
  for (int i = 0; i < m; ++i) f[u][i + 1][1 << i] = 1;
  for (int v : G[u])
    if (v != fa) {
      dp(v, u);
      for (int S = (1 << m) - 1; S; --S)
        for (int i = 1; i <= m; ++i)
          if (S >> (i - 1) & 1)
            for (int j : G[i + n])
              if (!(S & g[i][j - n]))
                (f[u][i][S | g[i][j - n]] +=
                 1LL * f[u][i][S] * f[v][j - n][g[i][j - n]] % P) %= P;
    }
  for (int i = 1; i <= m; ++i) (res += f[u][i][(1 << m) - 1]) %= P;
}
int main() {
  scanf("%d", &n);
  for (int i = 1, a, b; i < n; ++i) {
    scanf("%d%d", &a, &b), G[a].push_back(b), G[b].push_back(a);
  }
  scanf("%d", &m);
  for (int i = 1, a, b; i < m; ++i) {
    scanf("%d%d", &a, &b), a += n, b += n;
    G[a].push_back(b), G[b].push_back(a);
  }
  for (int i = n + 1; i <= n + m; ++i)
    for (int j = n + 1; j <= n + m; ++j)
      if (i != j) g[i - n][j - n] = dfs(j, i);
  res = 0, dp(1, 0), ans = res, res = 0, dp(n + 1, 0);
  printf("%lld", 1LL * ans * inv(res) % P);
  return 0;
}