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, T = 8000, N = 2000 + 5, D = 1e9 + 7;
namespace HASH {
const int D = 1e9 + 7;
long long w1[M], w2[M];
int ra_32() { return RAND_MAX <= 32768 ? rand() : rand() * 32768 + rand(); }
void init(int m) {
  for (int i = 1; i <= m; ++i) {
    w1[i] = ra_32();
    w2[i] = ra_32();
  }
}
int *lk, n;
int h[M], q[M];
void dfs(int x) {
  for (int y = x + 1; y <= n; ++y)
    if ((lk[x] >> y) & 1) dfs(y);
  int t = 0;
  for (int y = x + 1; y <= n; ++y)
    if ((lk[x] >> y) & 1) q[++t] = h[y];
  sort(q + 1, q + t + 1);
  h[x] = 0;
  for (int i = 1; i <= t; ++i) h[x] ^= (q[i] * w1[i] + w2[i]) % D;
}
int get(int *_lk, int _n) {
  lk = _lk;
  n = _n;
  dfs(1);
  return h[1];
}
};  // namespace HASH
struct Tree {
  int lk[M], n, v;
  void get_v() { v = HASH::get(lk, n); }
};
int m, tot, be[M], en[M];
Tree tree[T];
map<int, int> dy;
void check() {
  tree[tot + 1].get_v();
  if (!dy.count(tree[tot + 1].v)) {
    ++tot;
    dy[tree[tot].v] = tot;
  }
}
int *trans[T];
namespace B {
vector<int> lk[M];
int dfn[M], tot;
void dfs(int x, int fr, int s) {
  dfn[x] = ++tot;
  for (auto y : lk[x])
    if (y != fr && ((s >> y - 1) & 1)) dfs(y, x, s);
}
void init() {
  for (int i = 1; i <= m - 1; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    lk[x].push_back(y);
    lk[y].push_back(x);
  }
  for (int sz = 1; sz <= m; ++sz) {
    be[sz] = ::tot + 1;
    for (int s = 0; s <= (1 << m) - 1; ++s)
      if (__builtin_popcount(s) == sz)
        for (int x = 1; x <= m; ++x)
          if ((s >> x - 1) & 1) {
            tot = 0;
            dfs(x, 0, s);
            if (tot != sz) break;
            tree[::tot + 1].n = sz;
            for (int i = 1; i <= sz; ++i) tree[::tot + 1].lk[i] = 0;
            for (int i = 1; i <= m; ++i)
              if ((s >> i - 1) & 1)
                for (auto j : lk[i])
                  if ((s >> j - 1) & 1)
                    if (dfn[i] < dfn[j])
                      tree[::tot + 1].lk[dfn[i]] |= 1 << dfn[j];
            check();
          }
    en[sz] = ::tot;
  }
}
};  // namespace B
namespace A {
int n;
vector<int> lk[N];
void init() {
  cin >> n;
  for (int i = 1; i <= n - 1; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    lk[x].push_back(y);
    lk[y].push_back(x);
  }
}
long long ans, dp[N][T];
int sz[N];
void dfs(int x, int fr) {
  sz[x] = 1;
  dp[x][1] = 1;
  for (auto y : lk[x])
    if (y != fr) {
      dfs(y, x);
      for (int i = min(m, sz[x]); i >= 1; --i)
        for (int hi = en[i]; hi >= be[i]; --hi) {
          long long v = dp[x][hi];
          if (!v) continue;
          for (int j = 1; j <= min(m - i, sz[y]); ++j)
            for (int hj = be[j]; hj <= en[j]; ++hj)
              (dp[x][trans[hi][hj]] += v * dp[y][hj]) %= D;
        }
      sz[x] += sz[y];
    }
  for (int i = be[m]; i <= en[m]; ++i) (ans += dp[x][i]) %= D;
}
void work() {
  dfs(1, 0);
  cout << ans;
}
};  // namespace A
int main() {
  A::init();
  cin >> m;
  HASH::init(m);
  B::init();
  for (int i = 1; i <= m; ++i)
    for (int hi = be[i]; hi <= en[i]; ++hi) trans[hi] = new int[en[m - i] + 1];
  for (int i = 1; i <= m; ++i)
    for (int j = 1; j <= m - i; ++j)
      for (int hi = be[i]; hi <= en[i]; ++hi)
        for (int hj = be[j]; hj <= en[j]; ++hj) {
          Tree nt = tree[hi];
          nt.n += j;
          nt.lk[1] |= 1 << i + 1;
          for (int x = 1; x <= j; ++x) nt.lk[i + x] = tree[hj].lk[x] << i;
          nt.get_v();
          trans[hi][hj] = dy[nt.v];
        }
  A::work();
}