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() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return x * f;
}
void wr(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) wr(x / 10);
  putchar('0' + x % 10);
}
const int MAXN = 1010, mod = 1e9 + 7;
inline void tmod(long long &x) { x %= mod; }
inline long long qpow(long long a, long long b) {
  long long res = 1;
  a %= mod;
  for (; b; b >>= 1, tmod(a *= a))
    if (b & 1) tmod(res *= a);
  return res;
}
inline long long ginv(long long x) { return qpow(x, mod - 2); }
int S, lg[1 << 12], son[MAXN];
long long dp[MAXN][1 << 12];
struct tree {
  struct tEdge {
    int v, next;
  } e[MAXN << 1];
  int front[MAXN], tcnt, n;
  inline void adde(int u, int v) {
    e[++tcnt] = {v, front[u]};
    front[u] = tcnt;
  }
  void get() {
    n = read();
    for (register int(i) = (1); i <= (n - 1); ++(i)) {
      int x = read(), y = read();
      adde(x, y);
      adde(y, x);
    }
  }
  void init(int u, int f) {
    son[u] = 0;
    for (register int(i) = front[(u)]; (i); (i) = e[(i)].next) {
      int v = e[i].v;
      if (v == f) continue;
      init(v, u);
      son[u] |= 1 << v - 1;
    }
  }
  void dfs(int u, int f) {
    dp[u][0] = 1;
    for (register int(kk) = front[(u)]; (kk); (kk) = e[(kk)].next) {
      int v = e[kk].v;
      if (v == f) continue;
      dfs(v, u);
      for (register int(i) = (S); i >= (0); --(i))
        if (dp[u][i]) {
          int t = dp[u][i];
          for (int tt = S ^ i; tt; tt -= tt & -tt) {
            int p = lg[tt & -tt];
            if (dp[v][son[p + 1]])
              tmod(dp[u][i | (1 << p)] += t * dp[v][son[p + 1]]);
          }
        }
    }
  }
} T1, T2;
int main() {
  T1.get();
  T2.get();
  S = (1 << T2.n) - 1;
  for (register int(i) = (0); i <= (T2.n - 1); ++(i)) lg[1 << i] = i;
  long long ans1 = 0, ans2 = 0;
  for (register int(i) = (1); i <= (T2.n); ++(i)) {
    memset((dp), 0, sizeof(dp));
    T2.init(i, 0);
    T1.dfs(1, 0);
    for (register int(j) = (1); j <= (T1.n); ++(j)) tmod(ans1 += dp[j][son[i]]);
  }
  T1 = T2;
  for (register int(i) = (1); i <= (T2.n); ++(i)) {
    memset((dp), 0, sizeof(dp));
    T2.init(i, 0);
    T1.dfs(1, 0);
    tmod(ans2 += dp[1][son[i]]);
  }
  printf("%lld\n", ans1 * ginv(ans2) % mod);
  return 0;
}