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>
#pragma GCC optimize("2,Ofast,inline")
const long long N = 1e5 + 10;
const long long inf = 0x3f3f3f;
const double eps = 1e-9;
using namespace std;
template <typename tp>
inline void read(tp &x) {
  x = 0;
  char c = getchar();
  bool f = 0;
  for (; c < '0' || c > '9'; f |= (c == '-'), c = getchar())
    ;
  for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar())
    ;
  if (f) x = -x;
}
const long long P[] = {2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43};
long long n, m, mod, ans, ha[22], siz[22], son[22], dp[4020][22], pre[22];
vector<long long> Map[4020], ma[22];
set<long long> s;
bool cmp(long long a, long long b) { return ha[a] < ha[b]; }
void get_hash(long long now, long long fa) {
  long long last = -1;
  vector<long long> vec;
  ha[now] = siz[now] = 1;
  for (auto to : ma[now]) {
    if (to == fa) continue;
    get_hash(to, now);
    siz[now] += siz[to];
    vec.push_back(to);
    son[now] |= (1 << to);
  }
  sort(vec.begin(), vec.end(), cmp);
  for (auto v : vec) {
    ha[now] = (ha[now] + ha[v] * P[siz[v] - 1] % mod) % mod;
    if (~last && ha[v] == ha[last]) pre[v] = last;
    last = v;
  }
}
void DP(long long now, long long fa) {
  for (auto to : Map[now]) {
    if (to == fa) continue;
    DP(to, now);
  }
  static long long flag[1 << 20], nxt[1 << 20];
  for (long long i = 0; i < m; i++) {
    for (long long s = son[i]; s; s = s - 1 & son[i]) nxt[s] = 0;
    nxt[0] = 1;
    for (auto to : Map[now]) {
      if (to == fa) continue;
      for (long long s = son[i]; s; s = s - 1 & son[i]) flag[s] = nxt[s];
      flag[0] = nxt[0];
      for (long long j = 0; j < m; j++)
        if ((son[i] & (1 << j)) && dp[to][j])
          for (long long s = son[i]; s; s = s - 1 & son[i])
            if (s & (1 << j) && (pre[j] == -1 || s & (1 << pre[j])))
              nxt[s] = (nxt[s] + flag[s ^ (1 << j)] * dp[to][j] % mod) % mod;
    }
    dp[now][i] = nxt[son[i]];
  }
}
signed main() {
  read(n);
  for (long long i = 1, u, v; i < n; i++)
    read(u), read(v), Map[u].push_back(v), Map[v].push_back(u);
  read(m);
  for (long long i = 1, u, v; i < m; i++)
    read(u), read(v), u--, v--, ma[u].push_back(v), ma[v].push_back(u);
  mod = 1e9 + 7;
  for (long long i = 0; i < m; i++) {
    memset(son, 0, sizeof(son));
    memset(pre, -1, sizeof(pre));
    get_hash(i, -1);
    if (s.count(ha[i])) continue;
    s.insert(ha[i]);
    DP(1, -1);
    for (long long j = 1; j <= n; j++) ans = (ans + dp[j][i]) % mod;
  }
  printf("%lld\n", ans);
  return 0;
}