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;
using vint = vector<long long>;
using pint = pair<long long, long long>;
using vpint = vector<pint>;
template <typename A, typename B>
inline void chmin(A& a, B b) {
  if (a > b) a = b;
}
template <typename A, typename B>
inline void chmax(A& a, B b) {
  if (a < b) a = b;
}
template <class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>& p) {
  ost << "{" << p.first << "," << p.second << "}";
  return ost;
}
template <class T>
ostream& operator<<(ostream& ost, const vector<T>& v) {
  ost << "{";
  for (long long i = 0; i < v.size(); i++) {
    if (i) ost << ",";
    ost << v[i];
  }
  ost << "}";
  return ost;
}
inline long long topbit(unsigned long long x) {
  return x ? 63 - __builtin_clzll(x) : -1;
}
inline long long popcount(unsigned long long x) {
  return __builtin_popcountll(x);
}
inline long long parity(unsigned long long x) { return __builtin_parity(x); }
template <uint32_t mod>
struct ModInt {
  uint32_t a;
  ModInt& s(uint32_t vv) {
    a = vv < mod ? vv : vv - mod;
    return *this;
  }
  ModInt(int64_t x = 0) { s(x % mod + mod); }
  ModInt& operator+=(const ModInt& x) { return s(a + x.a); }
  ModInt& operator-=(const ModInt& x) { return s(a + mod - x.a); }
  ModInt& operator*=(const ModInt& x) {
    a = uint64_t(a) * x.a % mod;
    return *this;
  }
  ModInt& operator/=(const ModInt& x) {
    *this *= x.inv();
    return *this;
  }
  ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
  ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
  ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
  ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
  bool operator==(const ModInt& x) const { return a == x.a; }
  bool operator!=(const ModInt& x) const { return a != x.a; }
  bool operator<(const ModInt& x) const { return a < x.a; }
  ModInt operator-() const { return ModInt() - *this; }
  ModInt pow(int64_t n) const {
    ModInt res(1), x(*this);
    while (n) {
      if (n & 1) res *= x;
      x *= x;
      n >>= 1;
    }
    return res;
  }
  ModInt inv() const { return pow(mod - 2); }
};
template <uint32_t mod>
istream& operator>>(istream& in, ModInt<mod>& a) {
  return (in >> a.a);
}
template <uint32_t mod>
ostream& operator<<(ostream& out, const ModInt<mod>& a) {
  return (out << a.a);
}
using mint = ModInt<1000000007>;
long long N;
long long M;
vint S[1111], T[22];
long long id[22][22];
pint mem[33];
mint dp[1111][33];
mint dp2[1 << 12];
mint ans;
void dfs(long long v, long long p) {
  for (auto u : S[v]) {
    if (u == p) continue;
    dfs(u, v);
  }
  for (long long i = 0; i < (M); i++) {
    long long cs = T[i].size();
    for (long long j = 0; j < (1 << cs); j++) dp2[j] = 0;
    dp2[0] = 1;
    for (auto u : S[v]) {
      if (u == p) continue;
      for (long long j = (1 << cs) - 1; j >= 0; j--) {
        for (long long k = 0; k < (cs); k++)
          if (!(j >> k & 1))
            dp2[j | (1 << k)] += dp2[j] * dp[u][id[i][T[i][k]]];
      }
    }
    ans += dp2[(1 << cs) - 1];
    for (long long k = 0; k < (cs); k++) {
      dp[v][id[T[i][k]][i]] = dp2[((1 << cs) - 1) ^ (1 << k)];
    }
  }
}
signed main() {
  cin >> N;
  for (long long i = 0; i < (N - 1); i++) {
    long long a, b;
    cin >> a >> b;
    a--;
    b--;
    S[a].push_back(b);
    S[b].push_back(a);
  }
  cin >> M;
  for (long long i = 0; i < (M - 1); i++) {
    long long a, b;
    cin >> a >> b;
    a--;
    b--;
    T[a].push_back(b);
    T[b].push_back(a);
    id[a][b] = i * 2;
    mem[i * 2] = pint(a, b);
    id[b][a] = i * 2 + 1;
    mem[i * 2 + 1] = pint(b, a);
  }
  dfs(0, -1);
  mint tmp = ans;
  ans = 0;
  for (long long i = 0; i < (M); i++) {
    S[i] = T[i];
  }
  for (long long i = 0; i < (M); i++)
    for (long long j = 0; j < (33); j++) dp[i][j] = 0;
  dfs(0, -1);
  ans = tmp / ans;
  cout << ans << endl;
  return 0;
}