#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &x) {
  int ch = 0, f = 0;
  x = 0;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = 1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
  if (f) x = -x;
}
const int N = 2005, mod = 1e9 + 7,
          base[11] = {11,  29,       53,        13, 89,   43,
                      233, 19260817, 998244353, 17, 65537};
map<int, int> mp;
vector<int> g[N], g2[N];
int hs[N], pre[N], son[N], dp[N][13], f[1 << 12], f1[1 << 12], n, m, ans, rt;
inline bool cmp(int x, int y) { return hs[x] < hs[y]; }
inline int dfs(int u, int fa) {
  vector<int> vec;
  for (int i = 0; i < (int)g2[u].size(); i++) {
    int v = g2[u][i];
    if (v == fa) continue;
    dfs(v, u), vec.push_back(v), son[u] |= (1 << (v - 1));
  }
  sort(vec.begin(), vec.end(), cmp);
  int res = 1, bs = base[0];
  for (int i = 0; i < (int)vec.size(); i++) {
    res = (1ll * res + hs[vec[i]] * bs) % mod;
    bs = 1ll * bs * base[i + 1] % mod;
    if (i && hs[vec[i]] == hs[vec[i - 1]]) pre[vec[i]] = vec[i - 1];
  }
  return hs[u] = res;
}
inline void dfs2(int u, int fa) {
  for (int i = 0; i < (int)g[u].size(); i++)
    if (g[u][i] != fa) dfs2(g[u][i], u);
  for (int x = 1; x <= m; x++) {
    for (int i = 0; i < (1 << m); i++) f[i] = 0;
    f[0] = 1;
    for (int i = 0; i < (int)g[u].size(); i++) {
      int v = g[u][i];
      if (v == fa) continue;
      for (int i = 0; i < (1 << m); i++) f1[i] = f[i];
      for (int j = 0; j < m; j++)
        if (((1 << j) & son[x]) && dp[v][j + 1]) {
          for (int s = (1 << m) - 1; s; s--)
            if (((1 << j) & s) && (s & son[x]) == s &&
                (!pre[j + 1] || ((1 << (pre[j + 1] - 1)) & s)))
              f[s] = (1ll * f[s] + 1ll * dp[v][j + 1] * f1[s ^ (1 << j)]) % mod;
        }
    }
    dp[u][x] = f[son[x]];
  }
  ans = (1ll * ans + dp[u][rt]) % mod;
}
int main() {
  read(n);
  for (int i = 1, x, y; i < n; i++) {
    read(x), read(y);
    g[x].push_back(y), g[y].push_back(x);
  }
  read(m);
  for (int i = 1, x, y; i < m; i++) {
    read(x), read(y);
    g2[x].push_back(y), g2[y].push_back(x);
  }
  for (rt = 1; rt <= m; rt++) {
    memset(pre, 0, sizeof(pre));
    memset(son, 0, sizeof(son));
    dfs(rt, 0);
    if (mp[hs[rt]]) continue;
    mp[hs[rt]] = 1;
    dfs2(1, 0);
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Please formulate a cpp solution to the following 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &x) {
  int ch = 0, f = 0;
  x = 0;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = 1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
  if (f) x = -x;
}
const int N = 2005, mod = 1e9 + 7,
          base[11] = {11,  29,       53,        13, 89,   43,
                      233, 19260817, 998244353, 17, 65537};
map<int, int> mp;
vector<int> g[N], g2[N];
int hs[N], pre[N], son[N], dp[N][13], f[1 << 12], f1[1 << 12], n, m, ans, rt;
inline bool cmp(int x, int y) { return hs[x] < hs[y]; }
inline int dfs(int u, int fa) {
  vector<int> vec;
  for (int i = 0; i < (int)g2[u].size(); i++) {
    int v = g2[u][i];
    if (v == fa) continue;
    dfs(v, u), vec.push_back(v), son[u] |= (1 << (v - 1));
  }
  sort(vec.begin(), vec.end(), cmp);
  int res = 1, bs = base[0];
  for (int i = 0; i < (int)vec.size(); i++) {
    res = (1ll * res + hs[vec[i]] * bs) % mod;
    bs = 1ll * bs * base[i + 1] % mod;
    if (i && hs[vec[i]] == hs[vec[i - 1]]) pre[vec[i]] = vec[i - 1];
  }
  return hs[u] = res;
}
inline void dfs2(int u, int fa) {
  for (int i = 0; i < (int)g[u].size(); i++)
    if (g[u][i] != fa) dfs2(g[u][i], u);
  for (int x = 1; x <= m; x++) {
    for (int i = 0; i < (1 << m); i++) f[i] = 0;
    f[0] = 1;
    for (int i = 0; i < (int)g[u].size(); i++) {
      int v = g[u][i];
      if (v == fa) continue;
      for (int i = 0; i < (1 << m); i++) f1[i] = f[i];
      for (int j = 0; j < m; j++)
        if (((1 << j) & son[x]) && dp[v][j + 1]) {
          for (int s = (1 << m) - 1; s; s--)
            if (((1 << j) & s) && (s & son[x]) == s &&
                (!pre[j + 1] || ((1 << (pre[j + 1] - 1)) & s)))
              f[s] = (1ll * f[s] + 1ll * dp[v][j + 1] * f1[s ^ (1 << j)]) % mod;
        }
    }
    dp[u][x] = f[son[x]];
  }
  ans = (1ll * ans + dp[u][rt]) % mod;
}
int main() {
  read(n);
  for (int i = 1, x, y; i < n; i++) {
    read(x), read(y);
    g[x].push_back(y), g[y].push_back(x);
  }
  read(m);
  for (int i = 1, x, y; i < m; i++) {
    read(x), read(y);
    g2[x].push_back(y), g2[y].push_back(x);
  }
  for (rt = 1; rt <= m; rt++) {
    memset(pre, 0, sizeof(pre));
    memset(son, 0, sizeof(son));
    dfs(rt, 0);
    if (mp[hs[rt]]) continue;
    mp[hs[rt]] = 1;
    dfs2(1, 0);
  }
  cout << ans << endl;
  return 0;
}

```