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;
int Num[13][13], H[13][13], n, m, cnt;
long long D[1010][200], Mod = 1000000007, U[200];
vector<int> G[1010], E[13], Ch[13][13], P[200];
vector<pair<int, int> > L[13];
void DFS1(int a, int pp, int rt) {
  int i;
  H[rt][a] = 0;
  for (i = 0; i < E[a].size(); i++) {
    if (E[a][i] == pp) continue;
    Ch[rt][a].push_back(E[a][i]);
    DFS1(E[a][i], a, rt);
    H[rt][a] = max(H[rt][a], H[rt][E[a][i]] + 1);
  }
  L[H[rt][a]].push_back(pair<int, int>(rt, a));
}
bool Same(pair<int, int> a, pair<int, int> b) {
  int i, rt1 = a.first, rt2 = b.first, x1 = a.second, x2 = b.second;
  vector<int> P1, P2;
  for (i = 0; i < Ch[rt1][x1].size(); i++) {
    P1.push_back(Num[rt1][Ch[rt1][x1][i]]);
  }
  for (i = 0; i < Ch[rt2][x2].size(); i++) {
    P2.push_back(Num[rt2][Ch[rt2][x2][i]]);
  }
  if (P1.size() != P2.size()) return false;
  if (P1.size() == 0) return true;
  sort(P1.begin(), P1.end());
  sort(P2.begin(), P2.end());
  for (i = 0; i < P1.size(); i++)
    if (P1[i] != P2[i]) return false;
  return true;
}
long long TP[2048];
void DFS2(int a, int pp) {
  int i, j, k, l, x;
  vector<int> C;
  for (i = 0; i < G[a].size(); i++) {
    if (G[a][i] == pp) continue;
    DFS2(G[a][i], a);
    C.push_back(G[a][i]);
  }
  for (i = 1; i <= cnt; i++) {
    int ct = P[i].size();
    if (C.size() < ct) continue;
    if (P[i].empty()) {
      D[a][i] = 1;
      continue;
    }
    for (j = 0; j < (1 << ct); j++) TP[j] = 0;
    TP[0] = 1;
    for (j = 0; j < C.size(); j++) {
      x = C[j];
      for (l = (1 << ct) - 1; l >= 0; l--) {
        if (!TP[l]) continue;
        for (k = 0; k < ct; k++) {
          if (l & (1 << k)) continue;
          long long t = D[x][P[i][k]];
          TP[l | (1 << k)] = (TP[l | (1 << k)] + TP[l] * t) % Mod;
        }
      }
    }
    D[a][i] = TP[(1 << ct) - 1] * U[i] % Mod;
  }
}
bool v[200];
int Calc(vector<int> &P) {
  int i, c = 0, r = 1, j;
  for (i = 0; i < P.size(); i++) {
    c++;
    if (i == P.size() - 1 || P[i] != P[i + 1]) {
      for (j = 1; j <= c; j++) r = r * j;
      c = 0;
    }
  }
  return r;
}
long long Pow(long long a, int b) {
  long long r = 1;
  while (b) {
    if (b & 1) r = r * a % Mod;
    a = a * a % Mod;
    b >>= 1;
  }
  return r;
}
int main() {
  int i, a, b, j, k;
  scanf("%d", &n);
  for (i = 1; i < n; i++) {
    scanf("%d%d", &a, &b);
    G[a].push_back(b);
    G[b].push_back(a);
  }
  scanf("%d", &m);
  for (i = 1; i < m; i++) {
    scanf("%d%d", &a, &b);
    E[a].push_back(b);
    E[b].push_back(a);
  }
  for (i = 1; i <= m; i++) {
    DFS1(i, 0, i);
  }
  for (i = 0; i < m; i++) {
    for (j = 0; j < L[i].size(); j++) {
      int rt = L[i][j].first, x = L[i][j].second;
      for (k = 0; k < j; k++) {
        if (Same(L[i][j], L[i][k])) {
          Num[rt][x] = Num[L[i][k].first][L[i][k].second];
          break;
        }
      }
      if (k == j) {
        Num[rt][x] = ++cnt;
        for (k = 0; k < Ch[rt][x].size(); k++)
          P[cnt].push_back(Num[rt][Ch[rt][x][k]]);
        if (!P[cnt].empty()) sort(P[cnt].begin(), P[cnt].end());
        U[cnt] = Pow(Calc(P[cnt]), Mod - 2);
      }
    }
  }
  DFS2(1, 0);
  long long res = 0;
  for (i = 1; i <= m; i++) {
    if (!v[Num[i][i]]) {
      v[Num[i][i]] = true;
      for (j = 1; j <= n; j++) res = (res + D[j][Num[i][i]]) % Mod;
    }
  }
  printf("%lld\n", res);
}