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;
const int M = 13, N = 1e3 + 3;
const long long Pr = 1e9 + 7;
vector<int> Hs, val;
vector<int> mtr;
map<pair<int, int>, int> cb;
map<int, int> to, sz;
int bg[M], ed[M], m;
void init() {
  Hs.push_back(0);
  mtr.push_back(0);
  bg[0] = ed[0] = 0;
  Hs.push_back(2);
  mtr.push_back(0);
  to[2] = sz[2] = bg[1] = ed[1] = 1;
  for (int no = 2; no <= m; ++no) {
    bg[no] = ed[no - 1] + 1;
    int lt = no - 1, rt = 1;
    while (rt <= m && lt >= 1) {
      val.clear();
      for (int i = bg[rt]; i <= ed[rt]; ++i) val.push_back(Hs[i]);
      sort(val.begin(), val.end());
      int L = bg[lt] - 1;
      for (int i = 0; i <= val.size() - 1; ++i) {
        int MT = val[i];
        while (L < ed[lt] && mtr[L + 1] <= MT) ++L;
        for (int j = bg[lt]; j <= L; ++j) {
          mtr.push_back(MT);
          int ha = Hs[j];
          ha ^= (1 << (lt + lt - 1));
          Hs.push_back((MT << (lt + lt - 1)) + (1 << (no + no - 1)) + ha);
          to[Hs.back()] = Hs.size() - 1;
        }
      }
      lt--, rt++;
    }
    ed[no] = Hs.size() - 1;
    for (int i = bg[no]; i <= ed[no]; ++i) sz[Hs[i]] = no;
  }
  for (int i = 1; i <= ed[m - 1]; ++i) {
    val.clear();
    int ha = Hs[i], I, len = (sz[ha] << 1);
    while (mtr[I = to[ha]] > 0) {
      val.push_back(mtr[I]);
      len -= (sz[val.back()] << 1);
      ha &= ((1 << len) - 1);
      ha |= (1 << (len - 1));
    }
    ha = Hs[i];
    for (int j = ed[m - sz[ha]]; j >= 1; --j) {
      int hb = Hs[j], K = val.size();
      int ad = 1;
      for (int k = 0; k <= (int)val.size() - 1; ++k) {
        int sbt = val[k];
        if (sbt < hb) {
          ad <<= (sz[hb] << 1);
          ad |= hb;
          K = k;
          break;
        } else {
          ad <<= (sz[sbt] << 1);
          ad |= sbt;
        }
      }
      if (K == val.size()) {
        ad <<= (sz[hb] << 1);
        ad |= hb;
      }
      for (int k = K; k <= (int)val.size() - 1; ++k) {
        int sbt = val[k];
        (ad <<= (sz[sbt] << 1)) |= sbt;
      }
      ad <<= 1;
      cb[make_pair(ha, hb)] = ad;
    }
  }
}
int n, tr[N];
long long ans;
vector<int> s[N], t[N], has;
vector<int>::iterator it;
map<int, long long> dp[N];
void dfs(int fa, int anc) {
  tr[fa] = 1;
  dp[fa][2] = 1;
  for (int i = s[fa].size() - 1; i >= 0; --i) {
    int son = s[fa][i];
    if (son != anc) {
      dfs(son, fa);
      for (int sum = m; sum >= 2; --sum)
        for (int cta = 1; cta <= sum - 1; ++cta) {
          int ctb = sum - cta;
          if (cta > tr[fa] || ctb > tr[son]) continue;
          for (int I = bg[cta]; I <= ed[cta]; ++I)
            for (int J = bg[ctb]; J <= ed[ctb]; ++J) {
              int A = Hs[I], B = Hs[J];
              (dp[fa][cb[make_pair(A, B)]] += dp[fa][A] * dp[son][B] % Pr) %=
                  Pr;
            }
        }
      tr[fa] += tr[son];
    }
  }
  for (int i = has.size() - 1; i >= 0; --i) (ans += dp[fa][has[i]]) %= Pr;
}
int ctalc(int fa, int anc) {
  tr[fa] = 1;
  vector<pair<int, int> > vct;
  vct.clear();
  for (int i = t[fa].size() - 1; i >= 0; --i) {
    int son = t[fa][i];
    if (son != anc) {
      vct.push_back(make_pair(ctalc(son, fa), son));
      tr[fa] += tr[son];
    }
  }
  int ans = 1;
  sort(vct.begin(), vct.end());
  for (int i = (int)vct.size() - 1; i >= 0; --i) {
    ans <<= (tr[vct[i].second] << 1);
    ans |= vct[i].first;
  }
  ans <<= 1;
  return ans;
}
int main() {
  scanf("%d", &n);
  for (int i = 2; i <= n; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    s[u].push_back(v);
    s[v].push_back(u);
  }
  scanf("%d", &m);
  for (int i = 2; i <= m; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    t[u].push_back(v);
    t[v].push_back(u);
  }
  init();
  for (int i = 1; i <= m; ++i) has.push_back(ctalc(i, 0));
  sort(has.begin(), has.end());
  it = unique(has.begin(), has.end());
  has.resize(distance(has.begin(), it));
  dfs(1, 0);
  printf("%lld\n", ans);
  return 0;
}