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 gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXSN = 1000;
const int MAXSM = MAXSN - 1;
const int MAXTN = 12;
const int MAXTM = MAXTN - 1;
const int MOD = 1000000007;
int sn;
int shead[MAXSN], snxt[2 * MAXSM], sto[2 * MAXSM];
int tn;
int thead[MAXTN], tnxt[2 * MAXTM], tto[2 * MAXTM];
int tsz[2 * MAXTM];
int calctsz(int x) {
  if (tsz[x] != 0)
    return tsz[x];
  else
    tsz[x] = 1;
  int at = tto[x];
  for (int y = thead[at]; y != -1; y = tnxt[y])
    if ((y ^ 1) != x) tsz[x] += calctsz(y);
  return tsz[x];
}
int memst[MAXSN + 2 * MAXSM][MAXTN + 2 * MAXTM];
int memtt[MAXTN + 2 * MAXTM][MAXTN + 2 * MAXTM];
int z[MAXTN], nz;
int dp[1 << MAXTN];
int calcst(int av, int pax, int bv, int pbx) {
  int aid = pax == -1 ? av : sn + pax, bid = pbx == -1 ? bv : tn + pbx;
  int &ret = memst[aid][bid];
  if (ret == -1) {
    ret = 0;
    for (int ax = shead[av]; ax != -1; ax = snxt[ax])
      if (pax == -1 || (ax ^ 1) != pax) {
        int aw = sto[ax];
        for (int bx = thead[bv]; bx != -1; bx = tnxt[bx])
          if (pbx == -1 || (bx ^ 1) != pbx) {
            int bw = tto[bx];
            calcst(aw, ax, bw, bx);
          }
      }
    int bx1 = -1, nbx1 = 0, bx2 = -1, nbx2 = 0;
    nz = 0;
    for (int bx = thead[bv]; bx != -1; bx = tnxt[bx])
      if (pbx == -1 || (bx ^ 1) != pbx) {
        if (tsz[bx] == 1)
          bx1 = bx, nbx1++;
        else if (tsz[bx] == 2)
          bx2 = bx, nbx2++;
        else
          z[nz++] = bx;
      }
    int n = (nbx1 + 1) * (nbx2 + 1) * (1 << nz);
    for (int i = (0); i < (n); ++i) dp[i] = 0;
    dp[0] = 1;
    for (int ax = shead[av]; ax != -1; ax = snxt[ax])
      if (pax == -1 || (ax ^ 1) != pax) {
        int aw = sto[ax];
        for (int k1 = nbx1; k1 >= 0; --k1)
          for (int k2 = nbx2; k2 >= 0; --k2)
            for (int kz = (1 << nz) - 1; kz >= 0; --kz) {
              int k = k1 + (nbx1 + 1) * (k2 + (nbx2 + 1) * kz);
              if (dp[k] == 0) continue;
              for (int j = (0); j < (nz + 2); ++j) {
                int nk1 = k1, nk2 = k2, nkz = kz, times = 1;
                int bx = j < nz ? z[j] : j == nz ? bx1 : bx2;
                if (bx == -1) continue;
                int bw = tto[bx];
                int cur = calcst(aw, ax, bw, bx);
                if (j < nz)
                  if (kz & (1 << j))
                    continue;
                  else
                    nkz |= 1 << j;
                if (j == nz)
                  if (k1 == nbx1)
                    continue;
                  else
                    ++nk1, times *= nbx1 - k1;
                if (j == nz + 1)
                  if (k2 == nbx2)
                    continue;
                  else
                    ++nk2, times *= nbx2 - k2;
                int nk = nk1 + (nbx1 + 1) * (nk2 + (nbx2 + 1) * nkz);
                dp[nk] = (dp[nk] + (long long)dp[k] * cur * times) % MOD;
              }
            }
      }
    ret = dp[n - 1];
  }
  return ret;
}
int calctt(int av, int pax, int bv, int pbx) {
  int aid = pax == -1 ? av : tn + pax, bid = pbx == -1 ? bv : tn + pbx;
  int &ret = memtt[aid][bid];
  if (ret == -1) {
    ret = 0;
    for (int ax = thead[av]; ax != -1; ax = tnxt[ax])
      if (pax == -1 || (ax ^ 1) != pax) {
        int aw = tto[ax];
        for (int bx = thead[bv]; bx != -1; bx = tnxt[bx])
          if (pbx == -1 || (bx ^ 1) != pbx) {
            int bw = tto[bx];
            calctt(aw, ax, bw, bx);
          }
      }
    int bx1 = -1, nbx1 = 0, bx2 = -1, nbx2 = 0;
    nz = 0;
    for (int bx = thead[bv]; bx != -1; bx = tnxt[bx])
      if (pbx == -1 || (bx ^ 1) != pbx) {
        if (tsz[bx] == 1)
          bx1 = bx, nbx1++;
        else if (tsz[bx] == 2)
          bx2 = bx, nbx2++;
        else
          z[nz++] = bx;
      }
    int n = (nbx1 + 1) * (nbx2 + 1) * (1 << nz);
    for (int i = (0); i < (n); ++i) dp[i] = 0;
    dp[0] = 1;
    for (int ax = thead[av]; ax != -1; ax = tnxt[ax])
      if (pax == -1 || (ax ^ 1) != pax) {
        int aw = tto[ax];
        for (int k1 = nbx1; k1 >= 0; --k1)
          for (int k2 = nbx2; k2 >= 0; --k2)
            for (int kz = (1 << nz) - 1; kz >= 0; --kz) {
              int k = k1 + (nbx1 + 1) * (k2 + (nbx2 + 1) * kz);
              if (dp[k] == 0) continue;
              for (int j = (0); j < (nz + 2); ++j) {
                int nk1 = k1, nk2 = k2, nkz = kz, times = 1;
                int bx = j < nz ? z[j] : j == nz ? bx1 : bx2;
                if (bx == -1) continue;
                int bw = tto[bx];
                int cur = calctt(aw, ax, bw, bx);
                if (j < nz)
                  if (kz & (1 << j))
                    continue;
                  else
                    nkz |= 1 << j;
                if (j == nz)
                  if (k1 == nbx1)
                    continue;
                  else
                    ++nk1, times *= nbx1 - k1;
                if (j == nz + 1)
                  if (k2 == nbx2)
                    continue;
                  else
                    ++nk2, times *= nbx2 - k2;
                int nk = nk1 + (nbx1 + 1) * (nk2 + (nbx2 + 1) * nkz);
                dp[nk] = (dp[nk] + (long long)dp[k] * cur * times) % MOD;
              }
            }
      }
    ret = dp[n - 1];
  }
  return ret;
}
int mypow(int x, int n) {
  int ret = 1;
  while (true) {
    if (n & 1) ret = (long long)ret * x % MOD;
    if ((n >>= 1) == 0) return ret;
    x = (long long)x * x % MOD;
  }
}
void run() {
  scanf("%d", &sn);
  for (int i = (0); i < (sn); ++i) shead[i] = -1;
  for (int i = (0); i < (sn - 1); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a, --b;
    snxt[2 * i + 0] = shead[a], shead[a] = 2 * i + 0, sto[2 * i + 0] = b,
                 snxt[2 * i + 1] = shead[b], shead[b] = 2 * i + 1,
                 sto[2 * i + 1] = a;
  }
  scanf("%d", &tn);
  for (int i = (0); i < (tn); ++i) thead[i] = -1;
  for (int i = (0); i < (tn - 1); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a, --b;
    tnxt[2 * i + 0] = thead[a], thead[a] = 2 * i + 0, tto[2 * i + 0] = b,
                 tnxt[2 * i + 1] = thead[b], thead[b] = 2 * i + 1,
                 tto[2 * i + 1] = a;
  }
  memset(tsz, 0, sizeof(tsz));
  for (int i = (0); i < (2 * (tn - 1)); ++i) calctsz(i);
  int cnt = 0;
  memset(memst, -1, sizeof(memst));
  for (int i = (0); i < (sn); ++i) {
    int cur = calcst(i, -1, 0, -1);
    if ((cnt += cur) >= MOD) cnt -= MOD;
  }
  int times = 0;
  memset(memtt, -1, sizeof(memtt));
  for (int i = (0); i < (tn); ++i) {
    int cur = calctt(i, -1, 0, -1);
    if ((times += cur) >= MOD) times -= MOD;
  }
  int ret = (long long)cnt * mypow(times, MOD - 2) % MOD;
  printf("%d\n", ret);
}
int main() {
  run();
  return 0;
}