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("O2")
using namespace std;
const int INF = 0x3f3f3f3f, N = (1 << 12) + 5, MOD = 1e9 + 7;
const int MAXN = 1001;
const int MAXV = 1 << 12;
int po2[N];
inline int Add(int x, int y) {
  x += y;
  if (x >= MOD)
    return x - MOD;
  else
    return x;
}
namespace IStream {
const int L = 1 << 15;
char buffer[L + 5], *s, *t;
inline char get_char() {
  if (s == t) {
    t = (s = buffer) + fread(buffer, 1, L, stdin);
    if (s == t) return EOF;
  }
  return *s++;
}
inline int get_int() {
  char c;
  int ret = 0;
  while (c = get_char(), c < '0' || c > '9')
    ;
  while (c >= '0' && c <= '9')
    ret = (ret << 1) + (ret << 3) + (c - '0'), c = get_char();
  return ret;
}
}  // namespace IStream
long long qpow(long long a, long long b) {
  long long res = 1;
  for (; b; b >>= 1, a = a * a % MOD)
    if (b & 1) res = res * a % MOD;
  return res;
}
class Tree {
 public:
  int n, siz[MAXN], bits[MAXN], st[MAXN][MAXN];
  vector<int> g[MAXN];
  void read() {
    n = IStream::get_int();
    for (int i = 1; i < n; i++) {
      int u, v;
      u = IStream::get_int();
      v = IStream::get_int();
      g[u].push_back(v), g[v].push_back(u);
    }
  }
  void dfs(int x, int _fa) {
    siz[x] = bits[x] = 0;
    for (auto v : g[x])
      if (v != _fa) {
        dfs(v, x);
        st[x][++siz[x]] = v;
        bits[x] |= po2[v - 1];
      }
  }
} s, t;
int vis[MAXN][MAXV], dp[MAXN][MAXV];
int dfs(int x, int th, int sta) {
  if (!th) return !sta;
  int son = s.st[x][th], &res = dp[son][sta];
  if (vis[son][sta]) return dp[son][sta];
  vis[son][sta] = 1;
  res = dfs(x, th - 1, sta);
  for (int i = 1; i <= t.n; i++)
    if (sta & po2[i - 1]) {
      res = (res + 1ll * dfs(x, th - 1, sta ^ po2[i - 1]) *
                       dfs(son, s.siz[son], t.bits[i])) %
            MOD;
    }
  return res;
}
int Solve(int cas = 0) {
  po2[0] = 1;
  for (int i = 1; i < 30; i++) po2[i] = po2[i - 1] * 2;
  s.read();
  t.read();
  s.dfs(1, 0);
  long long ans = 0, ans2 = 0;
  for (int i = 1; i <= t.n; i++) {
    memset(dp, 0, sizeof dp);
    memset(vis, 0, sizeof vis);
    t.dfs(i, 0);
    for (int j = 1; j <= s.n; j++) ans = Add(ans, dfs(j, s.siz[j], t.bits[i]));
  }
  s = t;
  s.dfs(1, 0);
  for (int i = 1; i <= t.n; i++) {
    memset(dp, 0, sizeof dp);
    memset(vis, 0, sizeof vis);
    t.dfs(i, 0);
    ans2 = Add(ans2, dfs(1, s.siz[1], t.bits[i]));
  }
  cout << ans * qpow(ans2, MOD - 2) % MOD << endl;
  return 0;
}
void Pre() {}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  Pre();
  while (Solve())
    ;
  return 0;
}