#include <bits/stdc++.h>
using namespace std;
template <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
static void redirect(int argc, const char **argv) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  if (argc > 1) {
    static filebuf f;
    f.open(argv[1], ios::in);
    cin.rdbuf(&f);
    if (!cin) {
      cerr << "Failed to open '" << argv[1] << "'" << endl;
      exit(1);
    }
  }
  if (argc > 2) {
    static filebuf f;
    f.open(argv[2], ios::out | ios::trunc);
    cout.rdbuf(&f);
    if (!cout) {
      cerr << "Failed to open '" << argv[2] << "'" << endl;
    }
  }
  cin.exceptions(ios::failbit);
}
template <typename T>
static constexpr T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <typename T>
static constexpr T wrap_pos(T a, T m) {
  return a < 0 ? a + m : a;
}
template <typename T>
static constexpr T sqr(T a) {
  return a * a;
}
template <typename T>
static constexpr T mod(T a, T m) {
  return wrap_pos(a % m, m);
}
template <typename T>
static constexpr T inverse2(T a, T m) {
  return a <= 1 ? a : mod((1 - inverse2(m % a, a) * m) / a, m);
}
template <typename T>
static constexpr T inverse(T a, T m) {
  return inverse2(mod(a, m), m);
}
template <typename T, typename P>
static constexpr T power(T a, P b) {
  return b == 0 ? T(1) : (b % 2) ? power(a, b - 1) * a : sqr(power(a, b / 2));
}
template <typename T, typename C, T Modulus>
class MR {
 private:
  struct tag_plus {};
  struct tag_minus {};
  struct tag_good {};
  T value;
  static_assert(std::numeric_limits<C>::max() / Modulus / Modulus > 0,
                "compute type is too small");
  static_assert(Modulus < std::numeric_limits<T>::max() / 2,
                "storage type is too small");
  static constexpr T reduce(T value, tag_plus) {
    return value >= Modulus ? value - Modulus : value;
  }
  static constexpr T reduce(T value, tag_minus) {
    return value < 0 ? value + Modulus : value;
  }
  static constexpr T reduce(T value, tag_good) { return value; }

 public:
  static constexpr T modulus = Modulus;
  constexpr MR() : value(0) {}
  constexpr MR(C value) : value(reduce(value % Modulus, tag_minus())) {}
  template <typename tag_t>
  constexpr MR(T value, tag_t tag) : value(reduce(value, tag)) {}
  MR &operator=(C value) {
    this->value = reduce(value % Modulus, tag_minus());
    return *this;
  }
  constexpr MR operator+(MR b) const { return MR(value + b.value, tag_plus()); }
  constexpr MR operator-(MR b) const {
    return MR(value - b.value, tag_minus());
  }
  constexpr MR operator*(MR b) const {
    return MR(C(value) * C(b.value) % Modulus, tag_good());
  }
  constexpr MR operator-() const { return MR(-value, tag_minus()); }
  MR &operator+=(MR b) {
    value = reduce(value + b.value, tag_plus());
    return *this;
  }
  MR &operator-=(MR b) {
    value = reduce(value - b.value, tag_minus());
    return *this;
  }
  MR &operator*=(MR b) {
    value = C(value) * C(b.value) % Modulus;
    return *this;
  }
  constexpr bool operator==(MR b) const { return value == b.value; }
  constexpr bool operator!=(MR b) const { return value != b.value; }
  constexpr T get() const { return value; }
  constexpr MR inverse() const {
    return MR(::inverse(C(value), C(Modulus)), tag_good());
  }
  constexpr MR operator/(MR b) const { return *this * b.inverse(); }
  MR &operator/=(MR b) { return *this *= b.inverse(); }
};
template <typename T, typename C, T Modulus>
static inline std::ostream &operator<<(std::ostream &o, MR<T, C, Modulus> mr) {
  return o << mr.get();
}
struct edge {
  int trg;
  int dual;
};
struct node {
  vector<edge> edges;
  vector<vector<MR<int, long long, 1000000007>>> counts;
};
static vector<node> load_tree() {
  int N;
  cin >> N;
  vector<node> nodes(N);
  for (int i = 0; i < N - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    nodes[u].edges.push_back(edge{v, ((int)(nodes[v].edges).size())});
    nodes[v].edges.push_back(edge{u, ((int)(nodes[u].edges).size()) - 1});
  }
  return nodes;
}
static int classify_r(const vector<node> &tree, int cur, int parent,
                      vector<vector<int>> &classes,
                      map<vector<int>, int> &class_map) {
  vector<int> c;
  for (const auto &e : tree[cur].edges)
    if (e.trg != parent)
      c.push_back(classify_r(tree, e.trg, cur, classes, class_map));
  sort(begin(c), end(c));
  if (!class_map.count(c)) {
    class_map[c] = ((int)(classes).size());
    classes.push_back(c);
  }
  return class_map[c];
}
static vector<vector<int>> classify(const vector<node> &tree) {
  vector<vector<int>> classes;
  map<vector<int>, int> class_map;
  classify_r(tree, 0, -1, classes, class_map);
  return classes;
}
static MR<int, long long, 1000000007> count_matches(
    vector<node> &tree, const vector<vector<int>> &classes) {
  int N = ((int)(tree).size());
  int C = ((int)(classes).size());
  for (int i = 0; i < N; i++)
    tree[i].counts.resize(((int)(tree[i].edges).size()) + 1,
                          vector<MR<int, long long, 1000000007>>(C));
  for (int c = 0; c < C; c++) {
    vector<int> freq(C);
    for (int y : classes[c]) freq[y]++;
    for (int i = 0; i < N; i++) {
      node &cur = tree[i];
      int E = ((int)(cur.edges).size());
      vector<map<vector<int>, MR<int, long long, 1000000007>>> pref(E + 1),
          suf(E + 1);
      pref[0][vector<int>(C)] = 1;
      for (int j = 0; j < E; j++) {
        const edge &e = cur.edges[j];
        pref[j + 1] = pref[j];
        for (const auto &v : pref[j])
          for (int k = 0; k < C; k++)
            if (v.first[k] < freq[k]) {
              vector<int> v2 = v.first;
              v2[k]++;
              pref[j + 1][v2] += v.second * tree[e.trg].counts[e.dual][k];
            }
      }
      suf[E][vector<int>(C)] = 1;
      for (int j = E - 1; j >= 0; j--) {
        const edge &e = cur.edges[j];
        suf[j] = suf[j + 1];
        for (const auto &v : suf[j + 1])
          for (int k = 0; k < C; k++)
            if (v.first[k] < freq[k]) {
              vector<int> v2 = v.first;
              v2[k]++;
              suf[j][v2] += v.second * tree[e.trg].counts[e.dual][k];
            }
      }
      for (int j = 0; j < E; j++) {
        MR<int, long long, 1000000007> total = 0;
        for (const auto &v1 : pref[j]) {
          vector<int> alt(C);
          for (int k = 0; k < C; k++) alt[k] = freq[k] - v1.first[k];
          auto ptr = suf[j + 1].find(alt);
          if (ptr != suf[j + 1].end()) total += v1.second * ptr->second;
        }
        cur.counts[j][c] = total;
      }
      cur.counts[E][c] = suf[0][freq];
    }
  }
  MR<int, long long, 1000000007> ans = 0;
  for (int i = 0; i < N; i++) ans += tree[i].counts.back().back();
  return ans;
}
static void solve() {
  vector<node> S = load_tree();
  vector<node> T = load_tree();
  vector<vector<int>> classes = classify(T);
  MR<int, long long, 1000000007> ans = count_matches(S, classes);
  MR<int, long long, 1000000007> div = count_matches(T, classes);
  ans /= div;
  cout << ans << '\n';
}
int main(int argc, const char **argv) {
  redirect(argc, argv);
  solve();
  return 0;
}

### Prompt

Generate 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>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
static void redirect(int argc, const char **argv) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  if (argc > 1) {
    static filebuf f;
    f.open(argv[1], ios::in);
    cin.rdbuf(&f);
    if (!cin) {
      cerr << "Failed to open '" << argv[1] << "'" << endl;
      exit(1);
    }
  }
  if (argc > 2) {
    static filebuf f;
    f.open(argv[2], ios::out | ios::trunc);
    cout.rdbuf(&f);
    if (!cout) {
      cerr << "Failed to open '" << argv[2] << "'" << endl;
    }
  }
  cin.exceptions(ios::failbit);
}
template <typename T>
static constexpr T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <typename T>
static constexpr T wrap_pos(T a, T m) {
  return a < 0 ? a + m : a;
}
template <typename T>
static constexpr T sqr(T a) {
  return a * a;
}
template <typename T>
static constexpr T mod(T a, T m) {
  return wrap_pos(a % m, m);
}
template <typename T>
static constexpr T inverse2(T a, T m) {
  return a <= 1 ? a : mod((1 - inverse2(m % a, a) * m) / a, m);
}
template <typename T>
static constexpr T inverse(T a, T m) {
  return inverse2(mod(a, m), m);
}
template <typename T, typename P>
static constexpr T power(T a, P b) {
  return b == 0 ? T(1) : (b % 2) ? power(a, b - 1) * a : sqr(power(a, b / 2));
}
template <typename T, typename C, T Modulus>
class MR {
 private:
  struct tag_plus {};
  struct tag_minus {};
  struct tag_good {};
  T value;
  static_assert(std::numeric_limits<C>::max() / Modulus / Modulus > 0,
                "compute type is too small");
  static_assert(Modulus < std::numeric_limits<T>::max() / 2,
                "storage type is too small");
  static constexpr T reduce(T value, tag_plus) {
    return value >= Modulus ? value - Modulus : value;
  }
  static constexpr T reduce(T value, tag_minus) {
    return value < 0 ? value + Modulus : value;
  }
  static constexpr T reduce(T value, tag_good) { return value; }

 public:
  static constexpr T modulus = Modulus;
  constexpr MR() : value(0) {}
  constexpr MR(C value) : value(reduce(value % Modulus, tag_minus())) {}
  template <typename tag_t>
  constexpr MR(T value, tag_t tag) : value(reduce(value, tag)) {}
  MR &operator=(C value) {
    this->value = reduce(value % Modulus, tag_minus());
    return *this;
  }
  constexpr MR operator+(MR b) const { return MR(value + b.value, tag_plus()); }
  constexpr MR operator-(MR b) const {
    return MR(value - b.value, tag_minus());
  }
  constexpr MR operator*(MR b) const {
    return MR(C(value) * C(b.value) % Modulus, tag_good());
  }
  constexpr MR operator-() const { return MR(-value, tag_minus()); }
  MR &operator+=(MR b) {
    value = reduce(value + b.value, tag_plus());
    return *this;
  }
  MR &operator-=(MR b) {
    value = reduce(value - b.value, tag_minus());
    return *this;
  }
  MR &operator*=(MR b) {
    value = C(value) * C(b.value) % Modulus;
    return *this;
  }
  constexpr bool operator==(MR b) const { return value == b.value; }
  constexpr bool operator!=(MR b) const { return value != b.value; }
  constexpr T get() const { return value; }
  constexpr MR inverse() const {
    return MR(::inverse(C(value), C(Modulus)), tag_good());
  }
  constexpr MR operator/(MR b) const { return *this * b.inverse(); }
  MR &operator/=(MR b) { return *this *= b.inverse(); }
};
template <typename T, typename C, T Modulus>
static inline std::ostream &operator<<(std::ostream &o, MR<T, C, Modulus> mr) {
  return o << mr.get();
}
struct edge {
  int trg;
  int dual;
};
struct node {
  vector<edge> edges;
  vector<vector<MR<int, long long, 1000000007>>> counts;
};
static vector<node> load_tree() {
  int N;
  cin >> N;
  vector<node> nodes(N);
  for (int i = 0; i < N - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    nodes[u].edges.push_back(edge{v, ((int)(nodes[v].edges).size())});
    nodes[v].edges.push_back(edge{u, ((int)(nodes[u].edges).size()) - 1});
  }
  return nodes;
}
static int classify_r(const vector<node> &tree, int cur, int parent,
                      vector<vector<int>> &classes,
                      map<vector<int>, int> &class_map) {
  vector<int> c;
  for (const auto &e : tree[cur].edges)
    if (e.trg != parent)
      c.push_back(classify_r(tree, e.trg, cur, classes, class_map));
  sort(begin(c), end(c));
  if (!class_map.count(c)) {
    class_map[c] = ((int)(classes).size());
    classes.push_back(c);
  }
  return class_map[c];
}
static vector<vector<int>> classify(const vector<node> &tree) {
  vector<vector<int>> classes;
  map<vector<int>, int> class_map;
  classify_r(tree, 0, -1, classes, class_map);
  return classes;
}
static MR<int, long long, 1000000007> count_matches(
    vector<node> &tree, const vector<vector<int>> &classes) {
  int N = ((int)(tree).size());
  int C = ((int)(classes).size());
  for (int i = 0; i < N; i++)
    tree[i].counts.resize(((int)(tree[i].edges).size()) + 1,
                          vector<MR<int, long long, 1000000007>>(C));
  for (int c = 0; c < C; c++) {
    vector<int> freq(C);
    for (int y : classes[c]) freq[y]++;
    for (int i = 0; i < N; i++) {
      node &cur = tree[i];
      int E = ((int)(cur.edges).size());
      vector<map<vector<int>, MR<int, long long, 1000000007>>> pref(E + 1),
          suf(E + 1);
      pref[0][vector<int>(C)] = 1;
      for (int j = 0; j < E; j++) {
        const edge &e = cur.edges[j];
        pref[j + 1] = pref[j];
        for (const auto &v : pref[j])
          for (int k = 0; k < C; k++)
            if (v.first[k] < freq[k]) {
              vector<int> v2 = v.first;
              v2[k]++;
              pref[j + 1][v2] += v.second * tree[e.trg].counts[e.dual][k];
            }
      }
      suf[E][vector<int>(C)] = 1;
      for (int j = E - 1; j >= 0; j--) {
        const edge &e = cur.edges[j];
        suf[j] = suf[j + 1];
        for (const auto &v : suf[j + 1])
          for (int k = 0; k < C; k++)
            if (v.first[k] < freq[k]) {
              vector<int> v2 = v.first;
              v2[k]++;
              suf[j][v2] += v.second * tree[e.trg].counts[e.dual][k];
            }
      }
      for (int j = 0; j < E; j++) {
        MR<int, long long, 1000000007> total = 0;
        for (const auto &v1 : pref[j]) {
          vector<int> alt(C);
          for (int k = 0; k < C; k++) alt[k] = freq[k] - v1.first[k];
          auto ptr = suf[j + 1].find(alt);
          if (ptr != suf[j + 1].end()) total += v1.second * ptr->second;
        }
        cur.counts[j][c] = total;
      }
      cur.counts[E][c] = suf[0][freq];
    }
  }
  MR<int, long long, 1000000007> ans = 0;
  for (int i = 0; i < N; i++) ans += tree[i].counts.back().back();
  return ans;
}
static void solve() {
  vector<node> S = load_tree();
  vector<node> T = load_tree();
  vector<vector<int>> classes = classify(T);
  MR<int, long long, 1000000007> ans = count_matches(S, classes);
  MR<int, long long, 1000000007> div = count_matches(T, classes);
  ans /= div;
  cout << ans << '\n';
}
int main(int argc, const char **argv) {
  redirect(argc, argv);
  solve();
  return 0;
}

```