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;
vector<int> s[1005], t[15];
unordered_map<int, vector<int>> mp;
unordered_map<int, int> f[1005];
int g[(1 << 12) + 5], h[(1 << 12) + 5];
int rasp = 0, m;
int nr(unsigned int num) { return 32 - __builtin_clz(num); }
int dfs(int nod, int ta) {
  vector<int> aux;
  for (auto it : t[nod])
    if (it != ta) aux.push_back(dfs(it, nod));
  sort(aux.begin(), aux.end());
  int cnt = 1;
  for (auto it : aux) cnt = (cnt << nr(it)) | it;
  cnt = cnt << 1;
  if (!mp.count(cnt)) mp[cnt] = aux;
  return cnt;
}
void dfs2(int nod, int ta) {
  for (auto it : s[nod])
    if (it != ta) dfs2(it, nod);
  int i, j, c;
  for (auto it : mp) {
    int x = it.first;
    vector<int>& y = it.second;
    int l = y.size();
    memset(g, 0, sizeof(int) * (1 << l));
    g[0] = 1;
    for (auto it2 : s[nod])
      if (it2 != ta) {
        memcpy(h, g, sizeof(int) * (1 << l));
        for (i = 0; i < l; i++)
          if (c = f[it2][y[i]])
            for (j = 0; j < (1 << l); j++)
              if (g[j] && !(j & (1 << i)) &&
                  !(i && y[i] == y[i - 1] && !(j & (1 << i - 1))))
                (h[j | (1 << i)] += 1LL * c * g[j] % 1000000007) %= 1000000007;
        memcpy(g, h, sizeof(int) * (1 << l));
      }
    f[nod][x] = g[(1 << l) - 1];
    if (nr(x) == 2 * m) (rasp += g[(1 << l) - 1]) %= 1000000007;
  }
}
int main() {
  int n, i, x, y;
  scanf("%d", &n);
  for (i = 1; i < n; i++) {
    scanf("%d%d", &x, &y);
    x--;
    y--;
    s[x].push_back(y);
    s[y].push_back(x);
  }
  scanf("%d", &m);
  for (i = 1; i < m; i++) {
    scanf("%d%d", &x, &y);
    x--;
    y--;
    t[x].push_back(y);
    t[y].push_back(x);
  }
  for (i = 0; i < m; i++) dfs(i, -1);
  dfs2(0, -1);
  printf("%d\n", rasp);
  return 0;
}