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;
long long dp[(long long)(1e3 + 5)][15][15], res, n0, dd[15][15], fac[15];
bool mk[(long long)(1e3 + 5)];
vector<int> g0[15], g[(long long)(1e3 + 5)];
vector<int> add;
long long qp(long long b, long long e) {
  if (!e) return 1;
  long long x = qp(b, e / 2);
  x = (x * x) % (long long)(1e9 + 7);
  if (e & 1) x = (x * b) % (long long)(1e9 + 7);
  return x;
}
pair<long long, long long> dfs(int u) {
  mk[u] = 1;
  vector<pair<long long, long long> > vals;
  vals.push_back(pair<long long, long long>(113, 113));
  map<pair<long long, long long>, int> fs;
  vector<pair<long long, pair<long long, long long> > > ss;
  for (auto y : g0[u])
    if (!mk[y]) {
      vals.push_back(dfs(y));
      fs[vals.back()]++;
      ss.push_back(
          pair<long long, pair<long long, long long> >(y, vals.back()));
    }
  sort((vals).begin(), (vals).end());
  if (vals.size() == g0[u].size() + 1) {
    dd[u][14] = 1;
    for (auto y : fs)
      dd[u][14] = (dd[u][14] * qp(fac[y.second], (long long)(1e9 + 7) - 2)) %
                  (long long)(1e9 + 7);
    for (auto y : ss)
      dd[u][y.first] = (dd[u][14] * fs[y.second]) % (long long)(1e9 + 7);
  }
  long long ans1 = 0;
  long long ans2 = 0;
  for (int i = 0; i < vals.size(); i++) {
    ans1 = (ans1 * 331 + vals[i].first * qp(fac[i], (long long)(1e9 + 7) - 2) +
            qp(i + 1000001, (long long)(1e9 + 7) - 2)) %
           (long long)(1e9 + 7);
    ans2 =
        (ans2 * 331 + vals[i].second * qp(fac[i], (long long)(2e9 + 99) - 2) +
         qp(i + 1000001, (long long)(2e9 + 99) - 2)) %
        (long long)(2e9 + 99);
  }
  return pair<long long, long long>(ans1, ans2);
}
void DP(int u) {
  mk[u] = 1;
  vector<int> sons;
  for (auto y : g[u])
    if (!mk[y]) {
      DP(y);
      sons.push_back(y);
    }
  int pos = 0;
  for (int i = 0; i < n0; i++) {
    long long dp0[2][(1 << g0[i].size())];
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < (1 << g0[i].size()); k++) dp0[j][k] = 0;
    dp0[0][0] = 1;
    for (int j = 0; j < sons.size(); j++) {
      int son = sons[j];
      int act = j & 1;
      int nex = 1 - (j & 1);
      for (int k = 0; k < (1 << g0[i].size()); k++) dp0[nex][k] = dp0[act][k];
      for (int ant = 0; ant < g0[i].size(); ant++)
        for (int mask = (1 << g0[i].size()) - 1; mask >= 0; mask--) {
          if (mask & (1 << ant)) continue;
          dp0[nex][mask | (1 << ant)] =
              (dp0[nex][mask | (1 << ant)] +
               dp0[act][mask] * dp[son][g0[i][ant]][i]) %
              (long long)(1e9 + 7);
        }
    }
    if (pos < add.size() && i == add[pos]) {
      res = (res + dp0[sons.size() & 1][(1 << g0[i].size()) - 1] * dd[i][14]) %
            (long long)(1e9 + 7);
      pos++;
    }
    for (int ant = 0; ant < g0[i].size(); ant++) {
      dp[u][i][g0[i][ant]] =
          (dp0[sons.size() & 1][(1 << g0[i].size()) - 1 - (1 << ant)] *
           dd[i][g0[i][ant]]) %
          (long long)(1e9 + 7);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  mt19937 rng(time(0));
  fac[0] = 1;
  for (int i = 1; i < 15; i++) fac[i] = (fac[i - 1] * i) % (long long)(1e9 + 7);
  int n, u, v;
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    cin >> u >> v;
    u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  cin >> n0;
  for (int i = 0; i < n0 - 1; i++) {
    cin >> u >> v;
    u--, v--;
    g0[u].push_back(v);
    g0[v].push_back(u);
  }
  set<pair<long long, long long> > oks;
  for (int i = 0; i < n0; i++) {
    pair<long long, long long> x = dfs(i);
    if (oks.find(x) == oks.end()) add.push_back(i);
    oks.insert(x);
    for (int j = 0; j < n0; j++) mk[j] = 0;
  }
  DP(0);
  cout << (res) << '\n';
  return 0;
}