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>
#pragma GCC optimize("O3")
using namespace std;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1LL;
  long long _ret = mypow(mul(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = mul(_ret, _a, _mod);
  return _ret;
}
long long mymul(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 0LL;
  long long _ret = mymul(add(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = add(_ret, _a, _mod);
  return _ret;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-9 && _x < _y + 1e-9;
}
int __ = 1, _cs;
void build() {}
struct Tree {
  int n;
  vector<int> v[1021];
  void init() {
    n = getint();
    for (int i = 1; i <= n; i++) v[i].clear();
    for (int i = 1; i < n; i++) {
      int ai = getint();
      int bi = getint();
      v[ai].push_back(bi);
      v[bi].push_back(ai);
    }
  }
} s, t;
int hsvl[1021], mid, con;
vector<int> v;
map<vector<int>, int> M;
int Hash(int x, int prt = -1) {
  vector<int> tv;
  for (int son : t.v[x]) {
    if (son == prt) continue;
    tv.push_back(Hash(son, x));
  }
  sort(tv.begin(), tv.end());
  if (M.count(tv) == 0) {
    M[tv] = ++mid;
    if (tv.empty()) con = mid;
  }
  return M[tv];
}
void init() {
  s.init();
  t.init();
}
vector<int> son[1021], vs[1021];
void pre_go(int now, int prt) {
  for (int x : s.v[now]) {
    if (x == prt) continue;
    vs[now].push_back(x);
    pre_go(x, now);
  }
}
vector<int> useful;
unordered_map<int, int> who;
int go(int now, int prt) {
  for (int tson : t.v[now]) {
    if (tson == prt) continue;
    son[now].push_back(go(tson, now));
  }
  sort(son[now].begin(), son[now].end());
  int ret = M[son[now]];
  useful.push_back(ret);
  who[ret] = now;
  return ret;
}
int target, ans, tdp[1 << 12], rdp[1 << 12];
int q[1 << 12], qt;
int iq[1 << 12], stmp;
unordered_map<int, int> dp[1021];
void go_cal(int now) {
  for (int sn : vs[now]) go_cal(sn);
  for (auto cv : useful) {
    if (cv == con) {
      dp[now][cv] = 1;
    } else {
      int he = who[cv];
      int csz = son[he].size();
      for (int j = 0; j < (1 << csz); j++) tdp[j] = 0;
      tdp[0] = 1;
      iq[0] = ++stmp;
      q[0] = 0;
      qt = 1;
      for (int sn : vs[now]) {
        for (int _ = 0; _ < qt; _++) rdp[q[_]] = tdp[q[_]];
        int cqt = qt;
        for (int _ = 0; _ < cqt; _++) {
          int inow = q[_];
          for (int j = 0; j < csz; j++) {
            if ((inow >> j) & 1) continue;
            if (j && son[he][j] == son[he][j - 1] &&
                ((inow >> (j - 1)) & 1) == 0)
              continue;
            tdp[inow | (1 << j)] =
                add(tdp[inow | (1 << j)], mul(rdp[inow], dp[sn][son[he][j]]));
            if (iq[inow | (1 << j)] != stmp) {
              iq[inow | (1 << j)] = stmp;
              q[qt++] = inow | (1 << j);
            }
          }
        }
      }
      dp[now][cv] = tdp[(1 << csz) - 1];
    }
    if (cv == target) ans = add(ans, dp[now][cv]);
  }
}
void cal(int i) {
  for (int j = 1; j <= t.n; j++) son[j].clear();
  who.clear();
  useful.clear();
  target = go(i, i);
  sort(useful.begin(), useful.end());
  useful.resize(unique(useful.begin(), useful.end()) - useful.begin());
  for (int j = 1; j <= s.n; j++) dp[j].clear();
  go_cal(1);
}
void solve() {
  pre_go(1, 1);
  for (int i = 1; i <= t.n; i++) {
    hsvl[i] = Hash(i);
    bool bye = false;
    for (int j = 1; j < i; j++)
      if (hsvl[i] == hsvl[j]) {
        bye = true;
        break;
      }
    if (bye) continue;
    cal(i);
  }
  printf("%d\n", ans);
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}