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 = 2010, B = 55;
int Mod, head[Maxn], size[22], m, n, g[2 * Maxn], nxt[2 * Maxn], cnt, root,
    p[22], t[22];
set<int> s;
long long H[22], F[1 << 15], GG[1 << 15], dp[Maxn][1 << 14], ans;
void addedge(int x, int y) {
  cnt++, g[cnt] = y;
  nxt[cnt] = head[x], head[x] = cnt;
}
bool cmp(int x, int y) { return H[x] < H[y]; }
int G[20][20];
void dfs1(int x, int fa) {
  vector<int> v;
  v.clear();
  size[x] = 1;
  for (int i = 1; i <= m; i++) {
    if (G[x][i] && i != fa) dfs1(i, x), v.push_back(i), size[x] += size[i];
  }
  H[x] = size[x];
  t[x] = 0;
  int w = 0;
  sort(v.begin(), v.end(), cmp);
  for (auto u : v) {
    H[x] = (1LL * H[x] * B % Mod + H[u]) % Mod;
    if (H[u] == H[w]) p[u] = w;
    w = u, t[x] |= 1 << u - 1;
  }
}
void dfs2(int x, int fa) {
  for (int i = head[x]; i; i = nxt[i]) {
    if (g[i] != fa) {
      dfs2(g[i], x);
    }
  }
  for (int u = 1; u <= m; u++) {
    for (int k = t[u]; k; k = t[u] & (k - 1)) F[k] = 0;
    F[0] = 1;
    for (int i = head[x]; i; i = nxt[i]) {
      if (g[i] != fa) {
        for (int k = t[u]; k; k = t[u] & (k - 1)) GG[k] = F[k];
        GG[0] = 1;
        for (int j = 1; j <= m; j++) {
          for (int S = t[u]; S; S = t[u] & (S - 1))
            if ((1 << j - 1) & S && ((!p[j]) || (1 << p[j] - 1) & S)) {
              (F[S] += GG[(1 << j - 1) ^ S] * dp[g[i]][j] % Mod) %= Mod;
            }
        }
      }
    }
    dp[x][u] = F[t[u]];
  }
  (ans += dp[x][root]) %= Mod;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    addedge(x, y);
    addedge(y, x);
  }
  scanf("%d", &m);
  for (int i = 1; i < m; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    G[x][y] = 1, G[y][x] = 1;
  }
  Mod = 1e9 + 7;
  for (int i = 1; i <= m; i++) {
    memset(p, 0, sizeof(p));
    dfs1(i, 0);
    if (!s.count(H[i])) {
      s.insert(H[i]);
      root = i;
      dfs2(1, 0);
    }
  }
  cout << ans;
}