#include <bits/stdc++.h>
using namespace std;
const int MOD = 1E9 + 7;
int Add(int a, int b, int m = MOD) {
  a += b;
  if (a >= m) a -= m;
  return a;
}
int Sub(int a, int b, int m = MOD) {
  a -= b;
  if (a < 0) a += m;
  return a;
}
int AddTo(int& to, int w, int m = MOD) {
  to += w;
  if (to >= m) to -= m;
  return to;
}
int SubTo(int& to, int w, int m = MOD) {
  to -= w;
  if (to < 0) to += m;
  return to;
}
int Mult(int a, int b, int m = MOD) { return (a * 1LL * b) % m; }
int Pow(int a, long long deg, int m = MOD) {
  int res = 1 % m;
  for (; deg > 0; deg >>= 1, a = Mult(a, a, m))
    if (deg & 1) res = Mult(res, a, m);
  return res;
}
int Oem(int to, int m = MOD) { return Pow(to, m - 2, m); }
int Div(int a, int b, int m = MOD) { return Mult(a, Oem(b, m), m); }
int ns, nt;
vector<vector<int> > s, t;
void AddEdge(vector<vector<int> >& g, int f, int t) {
  g[f].push_back(t), g[t].push_back(f);
}
void RemEdge(vector<vector<int> >& g, int f, int t) {
  if (f == -1 || t == -1) return;
  g[f].erase(find(g[f].begin(), g[f].end(), t));
}
int na;
vector<vector<int> > a;
vector<int> best_p, path;
void Dfs(int vr, int par) {
  path.push_back(vr);
  if (((int)(path).size()) > ((int)(best_p).size())) best_p = path;
  for (int nxt : t[vr])
    if (nxt != par) Dfs(nxt, vr);
  path.pop_back();
}
pair<int, int> Center() {
  for (int i = 0; i < ((int)(t).size()); ++i) Dfs(i, -1);
  int m = ((int)(best_p).size()) / 2;
  if (((int)(best_p).size()) & 1)
    return make_pair(best_p[m], best_p[m]);
  else
    return make_pair(best_p[m - 1], best_p[m]);
}
map<vector<int>, int> names;
int Name(const vector<int>& l) {
  if (names.count(l)) return names[l];
  return names[l] = ((int)(names).size()) - 1;
}
int iso = 1;
int fact[15];
int AutoDfs(int vr, int par = -1) {
  vector<int> ch;
  for (int nxt : a[vr])
    if (nxt != par) ch.push_back(AutoDfs(nxt, vr));
  sort(ch.begin(), ch.end());
  for (int i = 0; i < ((int)(ch).size());) {
    int j = i;
    while (j < ((int)(ch).size()) && ch[i] == ch[j]) ++j;
    iso = Mult(iso, fact[j - i]);
    i = j;
  }
  return Name(ch);
}
int Auto() {
  fact[0] = 1;
  for (int i = 1; i < 15; ++i) fact[i] = Mult(i, fact[i - 1]);
  auto c = Center();
  a = t;
  int root = c.first;
  if (c.first != c.second) {
    RemEdge(a, c.first, c.second);
    RemEdge(a, c.second, c.first);
    a.push_back(vector<int>());
    AddEdge(a, ((int)(a).size()) - 1, c.first);
    AddEdge(a, ((int)(a).size()) - 1, c.second);
    root = ((int)(a).size()) - 1;
  }
  AutoDfs(root);
  return iso;
}
vector<vector<int> > base, put;
int dp[1000][12];
void Orient(vector<vector<int> >& g, int vr, int par = -1) {
  RemEdge(g, vr, par);
  for (int nxt : g[vr]) Orient(g, nxt, vr);
}
int dps[1010][1 << 11], dps_c = 0;
int Eval(int bvr, int pvr) {
  if (dp[bvr][pvr] != -1) return dp[bvr][pvr];
  int c = ((int)(put[pvr]).size());
  int* cdp = dps[dps_c++];
  memset(cdp, 0, (1 << c) * sizeof(int));
  cdp[0] = 1;
  for (int nxt : base[bvr]) {
    for (int msk = (1 << c) - 1; msk > 0; --msk) {
      for (int i = 0; i < c; ++i)
        if ((msk & (1 << i)) && cdp[msk ^ (1 << i)] != 0)
          AddTo(cdp[msk], Mult(cdp[msk ^ (1 << i)], Eval(nxt, put[pvr][i])));
    }
  }
  --dps_c;
  return dp[bvr][pvr] = cdp[(1 << c) - 1];
}
int Count(int proot) {
  memset(dp, -1, sizeof dp);
  base = s, put = t;
  Orient(base, 0);
  Orient(put, proot);
  int tot = 0;
  for (int i = 0; i < ((int)(base).size()); ++i) AddTo(tot, Eval(i, proot));
  return tot;
}
int main() {
  scanf("%d", &ns);
  s.resize(ns);
  for (int i = 1, x, y; i < ns; ++i)
    scanf("%d%d", &x, &y), AddEdge(s, x - 1, y - 1);
  scanf("%d", &nt);
  t.resize(nt);
  for (int i = 1, x, y; i < nt; ++i)
    scanf("%d%d", &x, &y), AddEdge(t, x - 1, y - 1);
  Auto();
  int total = 0;
  for (int i = 0; i < nt; ++i) AddTo(total, Count(i));
  printf("%d\n", Div(total, iso));
  return 0;
}

### Prompt

Your challenge is to write 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;
const int MOD = 1E9 + 7;
int Add(int a, int b, int m = MOD) {
  a += b;
  if (a >= m) a -= m;
  return a;
}
int Sub(int a, int b, int m = MOD) {
  a -= b;
  if (a < 0) a += m;
  return a;
}
int AddTo(int& to, int w, int m = MOD) {
  to += w;
  if (to >= m) to -= m;
  return to;
}
int SubTo(int& to, int w, int m = MOD) {
  to -= w;
  if (to < 0) to += m;
  return to;
}
int Mult(int a, int b, int m = MOD) { return (a * 1LL * b) % m; }
int Pow(int a, long long deg, int m = MOD) {
  int res = 1 % m;
  for (; deg > 0; deg >>= 1, a = Mult(a, a, m))
    if (deg & 1) res = Mult(res, a, m);
  return res;
}
int Oem(int to, int m = MOD) { return Pow(to, m - 2, m); }
int Div(int a, int b, int m = MOD) { return Mult(a, Oem(b, m), m); }
int ns, nt;
vector<vector<int> > s, t;
void AddEdge(vector<vector<int> >& g, int f, int t) {
  g[f].push_back(t), g[t].push_back(f);
}
void RemEdge(vector<vector<int> >& g, int f, int t) {
  if (f == -1 || t == -1) return;
  g[f].erase(find(g[f].begin(), g[f].end(), t));
}
int na;
vector<vector<int> > a;
vector<int> best_p, path;
void Dfs(int vr, int par) {
  path.push_back(vr);
  if (((int)(path).size()) > ((int)(best_p).size())) best_p = path;
  for (int nxt : t[vr])
    if (nxt != par) Dfs(nxt, vr);
  path.pop_back();
}
pair<int, int> Center() {
  for (int i = 0; i < ((int)(t).size()); ++i) Dfs(i, -1);
  int m = ((int)(best_p).size()) / 2;
  if (((int)(best_p).size()) & 1)
    return make_pair(best_p[m], best_p[m]);
  else
    return make_pair(best_p[m - 1], best_p[m]);
}
map<vector<int>, int> names;
int Name(const vector<int>& l) {
  if (names.count(l)) return names[l];
  return names[l] = ((int)(names).size()) - 1;
}
int iso = 1;
int fact[15];
int AutoDfs(int vr, int par = -1) {
  vector<int> ch;
  for (int nxt : a[vr])
    if (nxt != par) ch.push_back(AutoDfs(nxt, vr));
  sort(ch.begin(), ch.end());
  for (int i = 0; i < ((int)(ch).size());) {
    int j = i;
    while (j < ((int)(ch).size()) && ch[i] == ch[j]) ++j;
    iso = Mult(iso, fact[j - i]);
    i = j;
  }
  return Name(ch);
}
int Auto() {
  fact[0] = 1;
  for (int i = 1; i < 15; ++i) fact[i] = Mult(i, fact[i - 1]);
  auto c = Center();
  a = t;
  int root = c.first;
  if (c.first != c.second) {
    RemEdge(a, c.first, c.second);
    RemEdge(a, c.second, c.first);
    a.push_back(vector<int>());
    AddEdge(a, ((int)(a).size()) - 1, c.first);
    AddEdge(a, ((int)(a).size()) - 1, c.second);
    root = ((int)(a).size()) - 1;
  }
  AutoDfs(root);
  return iso;
}
vector<vector<int> > base, put;
int dp[1000][12];
void Orient(vector<vector<int> >& g, int vr, int par = -1) {
  RemEdge(g, vr, par);
  for (int nxt : g[vr]) Orient(g, nxt, vr);
}
int dps[1010][1 << 11], dps_c = 0;
int Eval(int bvr, int pvr) {
  if (dp[bvr][pvr] != -1) return dp[bvr][pvr];
  int c = ((int)(put[pvr]).size());
  int* cdp = dps[dps_c++];
  memset(cdp, 0, (1 << c) * sizeof(int));
  cdp[0] = 1;
  for (int nxt : base[bvr]) {
    for (int msk = (1 << c) - 1; msk > 0; --msk) {
      for (int i = 0; i < c; ++i)
        if ((msk & (1 << i)) && cdp[msk ^ (1 << i)] != 0)
          AddTo(cdp[msk], Mult(cdp[msk ^ (1 << i)], Eval(nxt, put[pvr][i])));
    }
  }
  --dps_c;
  return dp[bvr][pvr] = cdp[(1 << c) - 1];
}
int Count(int proot) {
  memset(dp, -1, sizeof dp);
  base = s, put = t;
  Orient(base, 0);
  Orient(put, proot);
  int tot = 0;
  for (int i = 0; i < ((int)(base).size()); ++i) AddTo(tot, Eval(i, proot));
  return tot;
}
int main() {
  scanf("%d", &ns);
  s.resize(ns);
  for (int i = 1, x, y; i < ns; ++i)
    scanf("%d%d", &x, &y), AddEdge(s, x - 1, y - 1);
  scanf("%d", &nt);
  t.resize(nt);
  for (int i = 1, x, y; i < nt; ++i)
    scanf("%d%d", &x, &y), AddEdge(t, x - 1, y - 1);
  Auto();
  int total = 0;
  for (int i = 0; i < nt; ++i) AddTo(total, Count(i));
  printf("%d\n", Div(total, iso));
  return 0;
}

```