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 Maxn = 1010, Maxm = 20;
const unsigned long long Seed = 19990213;
const long long Mod = 1000000007;
int n, m, cnt, tot1, fst1[Maxn], pre1[Maxn << 1], to1[Maxn << 1], tot2,
    fst2[Maxm], pre2[Maxm << 1], to2[Maxm << 1], bel[Maxm], tot[Maxm],
    stat[(1 << 12) + 10][Maxm], cur[Maxm], S, w[Maxm], size[Maxm];
bool vis[Maxn], leaf[Maxm];
long long f[Maxn][Maxm], g[Maxn][(1 << 12) + 10], ans;
unsigned long long ha[Maxm];
map<unsigned long long, bool> Hash;
vector<int> son[Maxn], sub[Maxm];
int Get() {
  char ch;
  int v = 0;
  bool f = false;
  while (!isdigit(ch = getchar()))
    if (ch == '-') f = true;
  v = ch - 48;
  while (isdigit(ch = getchar())) v = v * 10 + ch - 48;
  if (f)
    return -v;
  else
    return v;
}
void AddE1(int x, int y) {
  pre1[++tot1] = fst1[x], fst1[x] = tot1, to1[tot1] = y;
  pre1[++tot1] = fst1[y], fst1[y] = tot1, to1[tot1] = x;
}
void AddE2(int x, int y) {
  pre2[++tot2] = fst2[x], fst2[x] = tot2, to2[tot2] = y;
  pre2[++tot2] = fst2[y], fst2[y] = tot2, to2[tot2] = x;
}
bool cmp(const int &a, const int &b) {
  return ha[a] < ha[b] || (ha[a] == ha[b] && size[a] < size[b]);
}
void Add(long long &x, long long y) {
  x += y;
  if (x >= Mod) x -= Mod;
}
void Calc(int x, int fa) {
  leaf[x] = true, size[x] = 1;
  sub[x].clear();
  for (int i = fst2[x]; i; i = pre2[i])
    if (to2[i] != fa) {
      Calc(to2[i], x);
      size[x] += size[to2[i]];
      sub[x].push_back(to2[i]);
      leaf[x] = false;
    }
  if (leaf[x])
    ha[x] = 666072;
  else {
    ha[x] = 0;
    sort(sub[x].begin(), sub[x].end(), cmp);
    for (int i = 0; i < sub[x].size(); i++)
      ha[x] = (ha[x] * Seed + ha[sub[x][i]]) % Mod;
    ha[x] = ha[x] * 1234 % Mod;
  }
}
void Transform(int x, int w, int s) {
  if (x == cnt + 1) {
    S = max(S, s);
    for (int i = 1; i <= cnt; i++) stat[s][i] = cur[i];
    return;
  } else {
    for (int i = 0; i <= tot[x]; i++) {
      cur[x] = i;
      Transform(x + 1, w * (tot[x] + 1), s + i * w);
    }
  }
}
void dfs(int x) {
  vis[x] = true;
  son[x].clear();
  for (int i = fst1[x]; i; i = pre1[i])
    if (!vis[to1[i]]) son[x].push_back(to1[i]), dfs(to1[i]);
  int len1 = int(son[x].size());
  for (int i = 1; i <= m; i++)
    if (leaf[i])
      f[x][i] = 1;
    else if (len1 > 0) {
      f[x][i] = 0, cnt = 0, S = 0;
      int len2 = int(sub[i].size());
      for (int j = 0; j <= len2 - 1; j++) {
        bel[++cnt] = sub[i][j], tot[cnt] = 1;
        for (; j < len2 - 1 && ha[sub[i][j]] == ha[sub[i][j + 1]] &&
               size[sub[i][j]] == size[sub[i][j + 1]];
             j++)
          tot[cnt]++;
      }
      w[1] = 1;
      for (int j = 2; j <= cnt; j++) w[j] = w[j - 1] * (tot[j - 1] + 1);
      Transform(1, 1, 0);
      for (int s = 0; s <= S; s++) g[0][s] = 0;
      g[0][S] = 1;
      for (int j = 0; j <= len1 - 1; j++) {
        int u = son[x][j];
        for (int s = 0; s <= S; s++) g[j + 1][s] = g[j][s];
        for (int k = 1; k <= cnt; k++) {
          int v = bel[k];
          if (f[u][v]) {
            for (int s = 0; s <= S; s++)
              if (stat[s][k]) {
                Add(g[j + 1][s - w[k]], g[j][s] * f[u][v] % Mod);
              }
          }
        }
      }
      f[x][i] = g[len1][0];
    }
}
void solve(int root) {
  for (int i = 1; i <= n; i++) vis[i] = false;
  dfs(1);
  long long res = 0;
  for (int i = 1; i <= n; i++) {
    Add(ans, f[i][root]);
    Add(res, f[i][root]);
    for (int j = 1; j <= m; j++) f[i][j] = 0;
  }
}
int main() {
  n = Get();
  int x, y;
  for (int i = 1; i <= n - 1; i++) x = Get(), y = Get(), AddE1(x, y);
  m = Get();
  for (int i = 1; i <= m - 1; i++) x = Get(), y = Get(), AddE2(x, y);
  for (int i = 1; i <= m; i++) {
    Calc(i, -1);
    if (!Hash[ha[i]]) {
      Hash[ha[i]] = true;
      solve(i);
    }
  }
  cout << ans << endl;
  return 0;
}