762_F. Tree nesting_21747
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
#include <bits/stdc++.h>
using namespace std;
const int md = 1e9 + 7;
struct edge {
  int id1, id2;
};
edge e[2][11111];
const long long mod = (1e9 + 9) * (1e4 + 7);
const int a = 37, b = 1007, pn = 1e4 + 9, base = 67;
int n[2];
vector<int> adj[2][1111];
int dp[1 << 12], ww[1001][13], root, pr[1001];
bool can[1 << 12];
long long hs[13][13];
long long get_hash(int idx, int id, int pa) {
  long long res;
  vector<long long> now;
  now.clear();
  int i, j, s, p, q, ip;
  for (i = 0; i < adj[idx][id].size(); i++) {
    ip = adj[idx][id][i];
    if (ip == pa) continue;
    long long vl = get_hash(idx, ip, id);
    now.push_back(vl);
    hs[root][ip] = vl;
  }
  sort(now.begin(), now.end());
  res = a;
  for (i = 0; i < now.size(); i++) res = ((res * pn) ^ now[i]) % mod;
  res = (res * b) % mod;
  return res;
}
void got(int id, int pa) {
  int i, j, s, p, q, ip;
  pr[id] = pa;
  for (i = 0; i < adj[0][id].size(); i++) {
    ip = adj[0][id][i];
    if (ip == pa) continue;
    got(ip, id);
  }
}
int match(int id1, int id2, int pa1, int pa2) {
  int i, j, s, p, q, ip1, ip2;
  int pw[13], cnt = 0, ret = 0;
  for (i = 0; i < adj[1][id2].size(); i++) {
    ip2 = adj[1][id2][i];
    if (ip2 == pa2) continue;
    pw[cnt++] = ip2;
  }
  for (i = 0; i < adj[0][id1].size(); i++) {
    ip1 = adj[0][id1][i];
    if (ip1 == pa1) continue;
    for (j = 0; j < adj[1][id2].size(); j++) {
      ip2 = adj[1][id2][j];
      if (ip2 == pa2) continue;
      ww[ip1][ip2] = match(ip1, ip2, id1, id2);
    }
  }
  for (i = 0; i < (1 << cnt); i++) {
    dp[i] = 0;
    can[i] = true;
    for (j = 0; j < cnt && can[i]; j++) {
      if (!(i & (1 << j))) {
        for (s = j + 1; s < cnt && can[i]; s++) {
          if (i & (1 << s)) {
            if (hs[root][pw[j]] == hs[root][pw[s]]) can[i] = false;
          }
        }
      }
    }
  }
  dp[0] = 1;
  for (i = 0; i < adj[0][id1].size(); i++) {
    ip1 = adj[0][id1][i];
    if (ip1 == pa1) continue;
    for (j = (1 << cnt) - 1; j >= 0; j--) {
      if (dp[j] == 0) continue;
      for (s = 0; s < cnt; s++) {
        if (!(j & (1 << s)) && can[j | (1 << s)]) {
          dp[j | (1 << s)] +=
              (int)((long long)dp[j] * (long long)ww[ip1][pw[s]] % md);
          dp[j | (1 << s)] %= md;
        }
      }
    }
  }
  return dp[(1 << cnt) - 1];
}
int main() {
  int i, j, s, p, q, ans = 0;
  for (i = 0; i < 2; i++) {
    scanf("%d", &n[i]);
    for (j = 0; j < n[i] - 1; j++) {
      scanf("%d%d", &e[i][j].id1, &e[i][j].id2);
      e[i][j].id1--;
      e[i][j].id2--;
      adj[i][e[i][j].id1].push_back(e[i][j].id2);
      adj[i][e[i][j].id2].push_back(e[i][j].id1);
    }
  }
  for (i = 0; i < n[1]; i++) {
    root = i;
    hs[i][i] = get_hash(1, i, -1);
  }
  got(0, -1);
  for (i = 0; i < n[1]; i++) {
    for (j = 0; j < i; j++) {
      if (hs[i][i] == hs[j][j]) break;
    }
    if (j >= i) {
      memset(ww, 0, sizeof(ww));
      root = i;
      for (j = 0; j < n[0]; j++) ans = (ans + match(j, i, pr[j], -1)) % md;
    }
  }
  printf("%d\n", ans);
  return 0;
}
