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 = 2e9;
const long long Inf = 1e10;
const int P = 1e9 + 7;
const int N = 1005;
const int M = 14;
inline long long IN() {
  long long x = 0;
  int ch = 0, f = 0;
  for (ch = getchar(); ch != -1 && (ch < 48 || ch > 57); ch = getchar())
    f = (ch == '-');
  for (; ch >= 48 && ch <= 57; ch = getchar())
    x = (x << 1) + (x << 3) + ch - '0';
  return f ? (-x) : x;
}
template <typename T>
inline int chkmin(T &a, const T &b) {
  if (b < a) return a = b, 1;
  return 0;
}
template <typename T>
inline int chkmax(T &a, const T &b) {
  if (b > a) return a = b, 1;
  return 0;
}
void renew(int &x, const int &y) {
  x += y;
  if (x >= P) x -= P;
  if (x < 0) x += P;
}
int Pow(int x, int y, int p) {
  int a = 1;
  for (; y; y >>= 1, x = (long long)x * x % p)
    if (y & 1) a = (long long)a * x % p;
  return a;
}
int dp[N][M * M], tot;
map<vector<int>, int> mps;
int sz_info[N], chd_info[N];
vector<int> chd_hash[M * M];
vector<int> e[N], xe[N];
pair<int, int> dfs(int x, int y) {
  vector<int> s;
  int SZ = 1;
  for (auto v : xe[x]) {
    if (v == y) continue;
    pair<int, int> ret = dfs(v, x);
    SZ += ret.second;
    s.push_back(ret.first);
  }
  sort(s.begin(), s.end());
  int &v = mps[s];
  if (!v) {
    v = ++tot;
    sz_info[tot] = SZ;
    chd_info[tot] = s.size();
    chd_hash[tot] = s;
  }
  return pair<int, int>(v, SZ);
}
int m, n;
map<vector<int>, int> f, g;
int ans, ID[N];
vector<int> Has;
void calc(int x, int y) {
  int sn = 0;
  for (auto v : e[x]) {
    if (v == y) continue;
    calc(v, x);
    ++sn;
  }
  for (int stat = (int)(1); stat <= (int)(tot); stat++) {
    int tsz = chd_info[stat];
    if (sn < tsz) continue;
    int cnt = 0;
    f.clear();
    for (int i = (int)(0); i < (int)(tsz); i++) {
      int z = chd_hash[stat][i];
      if (ID[z] == -1) {
        ID[z] = cnt;
        Has.push_back(0);
        cnt++;
      }
      ++Has.back();
    }
    vector<int> NUL(cnt, 0);
    f[NUL] = 1;
    for (auto son : e[x]) {
      if (son == y) continue;
      g = f;
      for (int j = (int)(0); j < (int)(tsz); j++) {
        int v = chd_hash[stat][j], sv = v;
        if (j && v == chd_hash[stat][j - 1]) continue;
        v = ID[v];
        for (const auto &w : f) {
          auto st = w.first;
          int ways = (long long)w.second * dp[son][sv] % P;
          if (st[v] == Has[v]) continue;
          st[v]++;
          renew(g[st], ways);
        }
      }
      f = g;
    }
    dp[x][stat] = f[Has];
    if (sz_info[stat] == m) {
      renew(ans, dp[x][stat]);
    }
    Has.clear();
    for (int i = (int)(0); i < (int)(tsz); i++) ID[chd_hash[stat][i]] = -1;
  }
}
int main() {
  scanf("%d", &n);
  for (int i = (int)(1); i <= (int)(n - 1); i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    e[x].push_back(y);
    e[y].push_back(x);
  }
  scanf("%d", &m);
  for (int i = (int)(1); i <= (int)(m - 1); i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    xe[x].push_back(y);
    xe[y].push_back(x);
  }
  for (int i = (int)(1); i <= (int)(m); i++) dfs(i, 0);
  memset(ID, -1, sizeof ID);
  calc(1, 0);
  printf("%d\n", ans);
  return 0;
}