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 inf = 1.01e9;
const double eps = 1e-9;
const int N = 2010;
struct graph {
  int head[N], next[N], to[N], ec;
  int n;
  graph() { ec = 1; }
  inline void add(int x, int y) {
    ec += 1;
    to[ec] = y;
    next[ec] = head[x];
    head[x] = ec;
  }
  void read() {
    scanf("%d", &n);
    for (int i = 0; (i) < (n - 1); ++i) {
      int x, y;
      scanf("%d%d", &x, &y);
      --x, --y;
      add(x, y);
      add(y, x);
    }
  }
};
const int mod = 1e9 + 7;
int mpow(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) res = (res * (long long)a) % mod;
    a = (a * (long long)a) % mod;
    b >>= 1;
  }
  return res;
}
int mem[N][30];
graph g1, g2;
int d[13][(int)1e4];
int d2[13][(int)1e4];
int fact[13];
int get(int e1, int e2) {
  int &res = mem[e1][e2];
  if (res != -1) return res;
  vector<int> want;
  int ones = 0;
  for (int e = g2.head[g2.to[e2]]; e; e = g2.next[e])
    if ((e ^ e2) != 1) {
      if (g2.next[g2.head[g2.to[e]]] == 0)
        ones++;
      else
        want.push_back(e);
    }
  for (int e = g1.head[g1.to[e1]]; e; e = g1.next[e])
    if ((e ^ e1) != 1) {
      for (int i = 0; (i) < (((int)(want).size())); ++i) {
        int ee = want[i];
        get(e, ee);
      }
    }
  int SZ = (1LL << (((int)(want).size())));
  for (int j = 0; (j) < (ones + 1); ++j)
    for (int i = 0; (i) < (SZ); ++i) d[j][i] = 0;
  d[0][0] = 1;
  for (int e = g1.head[g1.to[e1]]; e; e = g1.next[e])
    if ((e ^ e1) != 1) {
      for (int z = 0; (z) < (ones + 1); ++z)
        for (int j = 0; (j) < (SZ); ++j) d2[z][j] = d[z][j];
      for (int i = 0; (i) < (((int)(want).size())); ++i) {
        int ee = want[i];
        int cnt = get(e, ee);
        if (cnt)
          for (int z = 0; (z) < (ones + 1); ++z)
            for (int j = 0; (j) < (SZ); ++j)
              if (!(j & (1LL << (i))))
                d2[z][j | (1LL << (i))] =
                    (d2[z][j | (1LL << (i))] + d[z][j] * (long long)cnt) % mod;
      }
      for (int z = 0; (z) < (ones); ++z)
        for (int j = 0; (j) < (SZ); ++j)
          d2[z + 1][j] = (d2[z + 1][j] + d[z][j] * (long long)(z + 1)) % mod;
      for (int z = 0; (z) < (ones + 1); ++z)
        for (int j = 0; (j) < (SZ); ++j) d[z][j] = d2[z][j];
    }
  return res = d[ones][SZ - 1];
}
int calc(graph gg1, graph gg2) {
  g1 = gg1, g2 = gg2;
  if (g2.n == 1) return g1.n;
  memset(mem, -1, sizeof mem);
  int res = 0;
  int fst = 0;
  for (int i = 0; (i) < (g2.n); ++i)
    if (g2.next[g2.head[i]] == 0) {
      fst = g2.head[i];
    }
  for (int e = 2; e <= g1.ec; ++e) {
    res = (res + get(e, fst)) % mod;
  }
  return res;
}
graph second, T;
int main() {
  fact[0] = 1;
  for (int i = 1; i < 13; ++i) fact[i] = fact[i - 1] * (long long)i % mod;
  second.read();
  T.read();
  int direct = calc(second, T);
  int indirect = calc(T, T);
  int res = direct * (long long)mpow(indirect, mod - 2) % mod;
  printf("%d\n", res);
  return 0;
}