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 N = 1010;
const int M = 12;
const int MOD = 1000000007;
int ans;
int n, m;
vector<int> S[N], T[M];
unordered_map<int, vector<int>> morph;
unordered_map<int, int> f[N];
int g[(1 << M) + 10], h[(1 << M) + 10];
inline int LEN(unsigned int t) { return 32 - __builtin_clz(t); }
int dfsT(int u, int fa) {
  vector<int> t;
  for (auto v : T[u])
    if (v != fa) t.push_back(dfsT(v, u));
  sort(t.begin(), t.end());
  int cc = 1;
  for (auto v : t) cc = (cc << LEN(v)) | v;
  cc <<= 1;
  if (!morph.count(cc)) morph[cc] = t;
  return cc;
}
void dfsS(int u, int fa) {
  for (auto v : S[u])
    if (v != fa) dfsS(v, u);
  for (auto current_morph : morph) {
    int ct = current_morph.first;
    vector<int> &st = current_morph.second;
    int l = st.size();
    memset(g, 0, sizeof(int) * (1 << l));
    g[0] = 1;
    for (auto v : S[u])
      if (v != fa) {
        memcpy(h, g, sizeof(int) * (1 << l));
        for (int i = 0, c; i < l; i++)
          if (c = f[v][st[i]])
            for (int j = 0; j < (1 << l); j++)
              if (g[j] && !(j & (1 << i)) &&
                  !(i && st[i] == st[i - 1] && !(j & (1 << i - 1))))
                (h[j | (1 << i)] += 1ll * c * g[j] % MOD) %= MOD;
        memcpy(g, h, sizeof(int) * (1 << l));
      }
    f[u][ct] = g[(1 << l) - 1];
    if (LEN(ct) == 2 * m) (ans += g[(1 << l) - 1]) %= MOD;
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1, u, v; i < n; i++) {
    scanf("%d%d", &u, &v);
    u--;
    v--;
    S[u].push_back(v);
    S[v].push_back(u);
  }
  scanf("%d", &m);
  for (int i = 1, u, v; i < m; i++) {
    scanf("%d%d", &u, &v);
    u--;
    v--;
    T[u].push_back(v);
    T[v].push_back(u);
  }
  for (int i = 0; i < m; i++) dfsT(i, -1);
  dfsS(0, -1);
  printf("%d\n", ans);
  return 0;
}