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>
const int MAXN = 1010;
const int MAXS = 1 << 12;
const int Dollar1 = 1000000007;
inline int up(int x) { return x -= Dollar1, x + (x >> 31 & Dollar1); }
inline int down(const int x) { return x + (x >> 31 & Dollar1); }
inline void add(int& x, const int y) {
  x += y - Dollar1, x += x >> 31 & Dollar1;
}
inline void dec(int& x, const int y) { x -= y, x += x >> 31 & Dollar1; }
inline int mul(const int x, const int y) {
  return static_cast<long long>(x) * y % Dollar1;
}
inline void mulr(int& x, const int y) {
  x = static_cast<long long>(x) * y % Dollar1;
}
int head[MAXN], nxt[MAXN << 1], to[MAXN << 1], tot;
inline void addedge(int b, int e) {
  nxt[++tot] = head[b];
  to[head[b] = tot] = e;
  nxt[++tot] = head[e];
  to[head[e] = tot] = b;
}
struct T {
  int head[12], nxt[12 << 1], to[12 << 1], tot;
  T() {
    memset(head, 0, sizeof head);
    tot = 0;
  }
  inline void addedge(int b, int e) {
    nxt[++tot] = head[b];
    to[head[b] = tot] = e;
    nxt[++tot] = head[e];
    to[head[e] = tot] = b;
  }
} tree;
int fac[20], inv[20];
int ha[13], rdc[13], fa[13];
std::vector<int> has[13];
int getha(int u, int f) {
  fa[u] = f;
  std::vector<int>& hal = has[u];
  hal.clear();
  for (int i = tree.head[u]; i; i = tree.nxt[i])
    if (tree.to[i] != f) hal.push_back(getha(tree.to[i], u));
  std::sort(hal.begin(), hal.end());
  int vha = 0, now = 13, lst = -1, cnt = 1, red = 1;
  for (int i : hal) {
    if (i == lst)
      ++cnt;
    else
      mulr(red, inv[cnt]), cnt = 1, lst = i;
    add(vha, mul(now, i)), mulr(now, 41);
  }
  mulr(red, inv[cnt]);
  add(vha, 1);
  rdc[u] = red;
  return ha[u] = vha;
}
int n, m, t1, t2;
int dp[MAXN][12];
int cnt[1 << 12];
std::set<int> vis;
int ans = 0;
int avai[12], RT;
void DP(int u, int f) {
  for (int i = head[u]; i; i = nxt[i])
    if (to[i] != f) DP(to[i], u);
  for (int i = 0; i != m; ++i) {
    memset(avai, -1, sizeof avai);
    int bak = 0;
    for (int j = tree.head[i]; j; j = tree.nxt[j])
      if (tree.to[j] != fa[i]) avai[tree.to[j]] = bak++;
    const int U = 1 << bak;
    memset(cnt, 0, U << 2);
    cnt[0] = 1;
    for (int j = head[u]; j; j = nxt[j])
      if (to[j] != f) {
        for (int k = U - 2; k >= 0; --k)
          if (cnt[k]) {
            for (int l = 0; l != m; ++l)
              if (~avai[l] && !(k >> avai[l] & 1))
                add(cnt[k | 1 << avai[l]], mul(cnt[k], dp[to[j]][l]));
          }
      }
    dp[u][i] = mul(cnt[U - 1], rdc[i]);
  }
  add(ans, dp[u][RT]);
}
int main() {
  fac[0] = fac[1] = inv[0] = inv[1] = 1;
  for (int i = 2; i != 20; ++i) {
    fac[i] = mul(fac[i - 1], i);
    inv[i] = mul(inv[Dollar1 % i], down(-Dollar1 / i));
  }
  for (int i = 2; i != 20; ++i) mulr(inv[i], inv[i - 1]);
  scanf("%d", &n);
  for (int i = 1; i != n; ++i) {
    scanf("%d%d", &t1, &t2);
    addedge(t1, t2);
  }
  scanf("%d", &m);
  for (int i = 1; i != m; ++i) {
    scanf("%d%d", &t1, &t2);
    tree.addedge(--t1, --t2);
  }
  for (int i = 0; i != m; ++i) {
    int HA = getha(i, -1);
    if (vis.find(HA) != vis.end()) continue;
    vis.insert(HA);
    memset(dp, 0, sizeof dp);
    RT = i;
    DP(1, 0);
  }
  printf("%d\n", ans);
  return 0;
}