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 Size = 1 << 16;
char buffer[Size], *head, *tail;
inline char Getchar() {
  if (head == tail) {
    int l = fread(buffer, 1, Size, stdin);
    tail = (head = buffer) + l;
  }
  if (head == tail) return -1;
  return *head++;
}
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
  return x * f;
}
const int maxn = 1010;
const int mod = 1000000007;
int n, first[maxn], nxt[maxn << 1], to[maxn << 1], cnt;
void AddEdge(int u, int v) {
  to[++cnt] = v;
  nxt[cnt] = first[u];
  first[u] = cnt;
  to[++cnt] = u;
  nxt[cnt] = first[v];
  first[v] = cnt;
}
int qpow(int n, int m) {
  int ans = 1;
  for (; m; m >>= 1, n = (long long)n * n % mod)
    if (m & 1) ans = (long long)ans * n % mod;
  return ans;
}
int f[maxn][13][13];
int m, e[13][13];
int son[13];
int g[1 << 13];
void dp(int x, int fa) {
  for (int i = first[x]; i; i = nxt[i])
    if (to[i] != fa) dp(to[i], x);
  for (int j = (1), j_end_ = (m); j <= j_end_; j++)
    for (int k = (0), k_end_ = (m); k <= k_end_; k++)
      if ((!k) || e[j][k]) {
        int& ans = f[x][j][k];
        int c = 0;
        for (int w = (1), w_end_ = (m); w <= w_end_; w++)
          if (e[j][w] && w != k) son[c++] = w;
        for (int S = (0), S_end_ = ((1 << c) - 1); S <= S_end_; S++) g[S] = 0;
        g[0] = 1;
        for (int i = first[x]; i; i = nxt[i])
          if (to[i] != fa) {
            for (int S = ((1 << c) - 1), S_end_ = (0); S >= S_end_; S--)
              for (int y = (0), y_end_ = (c - 1); y <= y_end_; y++)
                if (!(S >> y & 1)) {
                  (g[S ^ (1 << y)] +=
                   (long long)g[S] * f[to[i]][son[y]][j] % mod) %= mod;
                }
          }
        ans = g[(1 << c) - 1];
      }
}
int main() {
  n = read();
  for (int i = (2), i_end_ = (n); i <= i_end_; i++) AddEdge(read(), read());
  m = read();
  for (int i = (2), i_end_ = (m); i <= i_end_; i++) {
    int a = read(), b = read();
    e[a][b] = e[b][a] = 1;
  }
  dp(1, 0);
  int ans1 = 0;
  for (int i = (1), i_end_ = (n); i <= i_end_; i++)
    for (int j = (1), j_end_ = (m); j <= j_end_; j++)
      (ans1 += f[i][j][0]) %= mod;
  memset(f, 0, sizeof(f));
  memset(first, 0, sizeof(first));
  cnt = 0;
  n = m;
  for (int i = (1), i_end_ = (m); i <= i_end_; i++)
    for (int j = (i + 1), j_end_ = (m); j <= j_end_; j++)
      if (e[i][j]) AddEdge(i, j);
  dp(1, 0);
  int ans2 = 0;
  for (int i = (1), i_end_ = (n); i <= i_end_; i++)
    for (int j = (1), j_end_ = (m); j <= j_end_; j++)
      (ans2 += f[i][j][0]) %= mod;
  printf("%d\n", (long long)ans1 * qpow(ans2, mod - 2) % mod);
  return 0;
}