#include <bits/stdc++.h>
using namespace std;
template <class X, class Y>
void minimize(X &x, const Y &y) {
  if (x > y) x = y;
}
template <class X, class Y>
void maximize(X &x, const Y &y) {
  if (x < y) x = y;
}
template <class T>
T Abs(const T &x) {
  return (x < 0 ? -x : x);
}
const int MOD = (int)1e9 + 7;
void add(int &x, const int &y) {
  x += y;
  if (x >= MOD) x -= MOD;
}
class Tree {
 private:
  vector<vector<int> > adj, children;
  vector<vector<int> > numWay;
  int n;
  Tree *small;
  void dfs(int u, int par) {
    for (__typeof((adj[u]).begin()) it = (adj[u]).begin(); it != (adj[u]).end();
         it++)
      if (*it != par) {
        children[u].push_back(*it);
        dfs(*it, u);
      }
  }
  void dfsTree(int root) {
    for (int i = (1), _b = (n); i <= _b; i = i + 1) children[i].clear();
    dfs(root, -1);
  }
  int getNumMatch(int u, int v) {
    if (numWay[u][v] >= 0) return numWay[u][v];
    if (small->children[v].empty()) return numWay[u][v] = 1;
    if (small->children[v].size() > children[u].size()) return numWay[u][v] = 0;
    int numChild = small->children[v].size();
    vector<int> tmp((1LL << (numChild)), 0);
    tmp[0] = 1;
    for (__typeof((children[u]).begin()) it = (children[u]).begin();
         it != (children[u]).end(); it++) {
      vector<int> newDP = tmp;
      for (int i = 0, _n = ((1LL << (numChild))); i < _n; i = i + 1)
        for (int j = 0, _n = (numChild); j < _n; j = j + 1)
          if (!(((i) >> (j)) & 1))
            add(newDP[i | (1LL << (j))],
                1LL * tmp[i] * getNumMatch(*it, small->children[v][j]) % MOD);
      tmp = newDP;
    }
    return numWay[u][v] = tmp[(1LL << (numChild)) - 1];
  }
  int countMatch(int root, int smallRoot) {
    for (int i = (1), _b = (n); i <= _b; i = i + 1)
      for (int j = (1), _b = (small->n); j <= _b; j = j + 1) numWay[i][j] = -1;
    dfsTree(root);
    return getNumMatch(root, smallRoot);
  }
  int maxAdjNode(void) const {
    int res = 1;
    for (int i = (1), _b = (n); i <= _b; i = i + 1)
      if (adj[i].size() > adj[res].size()) res = i;
    return res;
  }

 public:
  Tree(int n = 0, vector<int> adj[] = NULL) {
    this->n = n;
    if (n == 0) return;
    this->adj.assign(n + 1, vector<int>());
    for (int i = (1), _b = (n); i <= _b; i = i + 1) this->adj[i] = adj[i];
    this->children.assign(n + 1, vector<int>());
    small = NULL;
  }
  int countMatch(Tree &small) {
    this->small = &small;
    int smallRoot = small.maxAdjNode();
    small.dfsTree(smallRoot);
    numWay.assign(n + 3, vector<int>(small.n + 3, 0));
    int res = 0;
    for (int i = (1), _b = (n); i <= _b; i = i + 1)
      res = (res + countMatch(i, smallRoot)) % MOD;
    return res;
  }
};
vector<int> bigAdj[1111], smallAdj[22];
int numBig, numSmall;
void readTree(int &n, vector<int> adj[]) {
  scanf("%d", &n);
  for (int love = 0, _n = (n - 1); love < _n; love = love + 1) {
    int u, v;
    scanf("%d%d", &u, &v);
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
}
void loadTree(void) {
  readTree(numBig, bigAdj);
  readTree(numSmall, smallAdj);
}
int inverse(int x) {
  int res = 1;
  int mul = x;
  int k = MOD - 2;
  while (k > 0) {
    if (k & 1) res = 1LL * res * mul % MOD;
    mul = 1LL * mul * mul % MOD;
    k >>= 1;
  }
  assert(1LL * res * x % MOD == 1);
  return res;
}
int process(void) {
  Tree bigTree(numBig, bigAdj);
  Tree smallTree(numSmall, smallAdj);
  Tree smallClone = smallTree;
  return 1LL * bigTree.countMatch(smallTree) *
         inverse(smallClone.countMatch(smallTree)) % MOD;
}
int main(void) {
  loadTree();
  cout << process() << endl;
  return 0;
}

### Prompt

Please create a solution in cpp 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 X, class Y>
void minimize(X &x, const Y &y) {
  if (x > y) x = y;
}
template <class X, class Y>
void maximize(X &x, const Y &y) {
  if (x < y) x = y;
}
template <class T>
T Abs(const T &x) {
  return (x < 0 ? -x : x);
}
const int MOD = (int)1e9 + 7;
void add(int &x, const int &y) {
  x += y;
  if (x >= MOD) x -= MOD;
}
class Tree {
 private:
  vector<vector<int> > adj, children;
  vector<vector<int> > numWay;
  int n;
  Tree *small;
  void dfs(int u, int par) {
    for (__typeof((adj[u]).begin()) it = (adj[u]).begin(); it != (adj[u]).end();
         it++)
      if (*it != par) {
        children[u].push_back(*it);
        dfs(*it, u);
      }
  }
  void dfsTree(int root) {
    for (int i = (1), _b = (n); i <= _b; i = i + 1) children[i].clear();
    dfs(root, -1);
  }
  int getNumMatch(int u, int v) {
    if (numWay[u][v] >= 0) return numWay[u][v];
    if (small->children[v].empty()) return numWay[u][v] = 1;
    if (small->children[v].size() > children[u].size()) return numWay[u][v] = 0;
    int numChild = small->children[v].size();
    vector<int> tmp((1LL << (numChild)), 0);
    tmp[0] = 1;
    for (__typeof((children[u]).begin()) it = (children[u]).begin();
         it != (children[u]).end(); it++) {
      vector<int> newDP = tmp;
      for (int i = 0, _n = ((1LL << (numChild))); i < _n; i = i + 1)
        for (int j = 0, _n = (numChild); j < _n; j = j + 1)
          if (!(((i) >> (j)) & 1))
            add(newDP[i | (1LL << (j))],
                1LL * tmp[i] * getNumMatch(*it, small->children[v][j]) % MOD);
      tmp = newDP;
    }
    return numWay[u][v] = tmp[(1LL << (numChild)) - 1];
  }
  int countMatch(int root, int smallRoot) {
    for (int i = (1), _b = (n); i <= _b; i = i + 1)
      for (int j = (1), _b = (small->n); j <= _b; j = j + 1) numWay[i][j] = -1;
    dfsTree(root);
    return getNumMatch(root, smallRoot);
  }
  int maxAdjNode(void) const {
    int res = 1;
    for (int i = (1), _b = (n); i <= _b; i = i + 1)
      if (adj[i].size() > adj[res].size()) res = i;
    return res;
  }

 public:
  Tree(int n = 0, vector<int> adj[] = NULL) {
    this->n = n;
    if (n == 0) return;
    this->adj.assign(n + 1, vector<int>());
    for (int i = (1), _b = (n); i <= _b; i = i + 1) this->adj[i] = adj[i];
    this->children.assign(n + 1, vector<int>());
    small = NULL;
  }
  int countMatch(Tree &small) {
    this->small = &small;
    int smallRoot = small.maxAdjNode();
    small.dfsTree(smallRoot);
    numWay.assign(n + 3, vector<int>(small.n + 3, 0));
    int res = 0;
    for (int i = (1), _b = (n); i <= _b; i = i + 1)
      res = (res + countMatch(i, smallRoot)) % MOD;
    return res;
  }
};
vector<int> bigAdj[1111], smallAdj[22];
int numBig, numSmall;
void readTree(int &n, vector<int> adj[]) {
  scanf("%d", &n);
  for (int love = 0, _n = (n - 1); love < _n; love = love + 1) {
    int u, v;
    scanf("%d%d", &u, &v);
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
}
void loadTree(void) {
  readTree(numBig, bigAdj);
  readTree(numSmall, smallAdj);
}
int inverse(int x) {
  int res = 1;
  int mul = x;
  int k = MOD - 2;
  while (k > 0) {
    if (k & 1) res = 1LL * res * mul % MOD;
    mul = 1LL * mul * mul % MOD;
    k >>= 1;
  }
  assert(1LL * res * x % MOD == 1);
  return res;
}
int process(void) {
  Tree bigTree(numBig, bigAdj);
  Tree smallTree(numSmall, smallAdj);
  Tree smallClone = smallTree;
  return 1LL * bigTree.countMatch(smallTree) *
         inverse(smallClone.countMatch(smallTree)) % MOD;
}
int main(void) {
  loadTree();
  cout << process() << endl;
  return 0;
}

```