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 long long N = 2100;
const long long M = 13;
const long long Mod = 1e9 + 7;
map<long long, long long> q;
long long head1[N], head2[N], maxE1, maxE2;
struct Edge {
  long long nxt, to;
} e1[N], e2[N];
long long n, m, ans, now, pro[N], pre[N], dp[N][M], tk1[1 << M], tk2[1 << M],
    crt[N];
const long long roe[12] = {11,  29,       53,        13, 89,   43,
                           233, 19260817, 998244353, 17, 65537};
inline long long read() {
  long long s = 0, w = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
  return s * w;
}
void print(long long x) {
  if (x > 9) print(x / 10);
  putchar(x % 10 + '0');
}
inline void Clear() {
  memset(pro, 0, sizeof(pro));
  memset(pre, 0, sizeof(pre));
}
inline void Add1(long long u, long long v) {
  e1[++maxE1].nxt = head1[u];
  head1[u] = maxE1;
  e1[maxE1].to = v;
}
inline void Add2(long long u, long long v) {
  e2[++maxE2].nxt = head2[u];
  head2[u] = maxE2;
  e2[maxE2].to = v;
}
bool cp(long long x, long long y) { return crt[x] < crt[y]; }
long long DFS(long long x, long long before) {
  vector<long long> q;
  for (long long i = head2[x]; i; i = e2[i].nxt) {
    if (e2[i].to == before) continue;
    DFS(e2[i].to, x);
    q.push_back(e2[i].to);
    pre[x] = pre[x] | (1ll << (e2[i].to - 1));
  }
  sort(q.begin(), q.end(), cp);
  long long s = 1, based = 23;
  for (long long i = 0; i < q.size(); i++) {
    s += based * crt[q[i]];
    s %= Mod;
    based *= roe[i];
    based %= Mod;
    if (!i || crt[q[i]] != crt[q[i - 1]]) continue;
    pro[q[i]] = q[i - 1];
  }
  return crt[x] = s;
}
void ASN(long long x, long long before) {
  for (long long i = head1[x]; i; i = e1[i].nxt)
    if (e1[i].to != before) ASN(e1[i].to, x);
  for (long long i = 1; i <= m; i++) {
    memset(tk1, 0, sizeof(tk1));
    tk1[0] = 1;
    for (long long j = head1[x]; j; j = e1[j].nxt) {
      if (e1[j].to == before) continue;
      memcpy(tk2, tk1, sizeof(tk2));
      for (long long k = 1; k <= m; k++) {
        if (!((1 << (k - 1)) & pre[i]) || !dp[e1[j].to][k]) continue;
        for (long long u = (1 << m) - 1; u; u--)
          if (((1 << (k - 1)) & u) && (u & pre[i]) == u &&
              (!pro[k] || ((1 << (pro[k] - 1)) & u))) {
            tk1[u] += dp[e1[j].to][k] * tk2[u ^ (1 << (k - 1))];
            tk1[u] %= Mod;
          }
      }
    }
    dp[x][i] = tk1[pre[i]];
  }
  ans += dp[x][now];
  ans %= Mod;
}
signed main() {
  n = read();
  for (long long i = 1, u, v; i < n; i++) {
    u = read();
    v = read();
    Add1(u, v);
    Add1(v, u);
  }
  m = read();
  for (long long i = 1, u, v; i < m; i++) {
    u = read();
    v = read();
    Add2(u, v);
    Add2(v, u);
  }
  for (long long i = 1; i <= m; i++) {
    Clear();
    now = i;
    DFS(i, 0);
    if (q[crt[i]]) continue;
    q[crt[i]] = 1;
    ASN(1, 0);
  }
  print(ans);
  putchar('\n');
  return 0;
}