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;
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (auto &v : vec) is >> v;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  for (int i = 0; i < vec.size(); i++) {
    os << vec[i];
    if (i + 1 != vec.size()) os << " ";
  }
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &st) {
  for (auto itr = st.begin(); itr != st.end(); ++itr) {
    os << *itr;
    auto titr = itr;
    if (++titr != st.end()) os << " ";
  }
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &st) {
  for (auto itr = st.begin(); itr != st.end(); ++itr) {
    os << *itr;
    auto titr = itr;
    if (++titr != st.end()) os << " ";
  }
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &st) {
  for (auto itr = st.begin(); itr != st.end(); ++itr) {
    os << *itr;
    auto titr = itr;
    if (++titr != st.end()) os << " ";
  }
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const unordered_multiset<T> &st) {
  for (auto itr = st.begin(); itr != st.end(); ++itr) {
    os << *itr;
    auto titr = itr;
    if (++titr != st.end()) os << " ";
  }
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
  for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
    os << "(" << itr->first << ", " << itr->second << ")";
    auto titr = itr;
    if (++titr != mp.end()) os << " ";
  }
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const unordered_map<T1, T2> &mp) {
  for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
    os << "(" << itr->first << ", " << itr->second << ")";
    auto titr = itr;
    if (++titr != mp.end()) os << " ";
  }
  return os;
}
using ll = long long int;
using P = pair<int, int>;
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;
const int mod = 1000000007;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
struct fast_io {
  fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(20);
  }
} fast_io_;
template <typename T>
T extgcd(T a, T b, T &x, T &y) {
  T d = a;
  if (b != 0) {
    d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  } else {
    x = 1, y = 0;
  }
  return d;
}
template <typename T>
T modinv(T a, T m) {
  long long x = 0, y = 0;
  extgcd<long long>(a, m, x, y);
  x %= m;
  if (x < 0) x += m;
  return x;
}
struct Tree {
  int n;
  vector<vector<int>> ed, child;
  Tree() {}
  void read() {
    cin >> n;
    ed.assign(n, vector<int>());
    for (int i = (0); i < (n - 1); ++i) {
      int u, v;
      cin >> u >> v, u--, v--;
      ed[u].emplace_back(v);
      ed[v].emplace_back(u);
    }
  }
  void dfs(int i, int p) {
    for (auto e : ed[i]) {
      if (e == p) continue;
      child[i].emplace_back(e);
      dfs(e, i);
    }
  }
  void dfs(int r) {
    child.assign(n, vector<int>());
    dfs(r, -1);
  }
  void out() {
    for (int i = (0); i < (n); ++i) {
      cerr << i << " " << child[i] << endl;
    }
  }
};
ll dp[1010][1 << 13];
ll memo[13][1010];
ll calc1(Tree &S, Tree &T, int v, int u) {
  if (memo[u][v] >= 0) return memo[u][v];
  if (((int)(T.child[u]).size()) == 0) return memo[u][v] = 1;
  if (((int)(S.child[v]).size()) == 0) return memo[u][v] = 0;
  vector<vector<ll>> cn(((int)(T.child[u]).size()),
                        vector<ll>(((int)(S.child[v]).size()), 0));
  for (int i = (0); i < (((int)(T.child[u]).size())); ++i) {
    for (int j = (0); j < (((int)(S.child[v]).size())); ++j) {
      cn[i][j] = calc1(S, T, S.child[v][j], T.child[u][i]);
    }
  }
  for (int i = (0); i < ((1 << ((int)(T.child[u]).size()))); ++i) dp[0][i] = 0;
  dp[0][0] = 1;
  for (int i = (0); i < (((int)(S.child[v]).size())); ++i) {
    for (int j = (0); j < ((1 << ((int)(T.child[u]).size()))); ++j)
      dp[i + 1][j] = 0;
    for (int j = (0); j < ((1 << ((int)(T.child[u]).size()))); ++j) {
      (dp[i + 1][j] += dp[i][j]) %= mod;
      for (int k = (0); k < (((int)(T.child[u]).size())); ++k) {
        if (!((j >> k) & 1)) {
          (dp[i + 1][j | (1 << k)] += dp[i][j] * cn[k][i] % mod) %= mod;
        }
      }
    }
  }
  return memo[u][v] = dp[((int)(S.child[v]).size())]
                        [(1 << ((int)(T.child[u]).size())) - 1];
}
int idx = 0;
ll calc(Tree &S, Tree &T) {
  ll ret = 0;
  for (int i = (0); i < (S.n); ++i) {
    S.dfs(i);
    for (int j = (0); j < (T.n); ++j)
      for (int k = (0); k < (S.n); ++k) memo[j][k] = -1;
    (ret += calc1(S, T, i, idx)) %= mod;
  }
  return ret;
}
int main(int argc, char const *argv[]) {
  Tree S, T, U;
  S.read();
  T.read();
  U = T;
  int maxi = 0;
  for (int i = (0); i < (T.n); ++i) {
    if (maxi < ((int)(T.ed[i]).size())) {
      idx = i;
      maxi = ((int)(T.ed[i]).size());
    }
  }
  T.dfs(idx);
  ll res = calc(S, T);
  res = res * modinv<ll>(calc(U, T), mod) % mod;
  cout << res << endl;
  return 0;
}