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 N = 2002;
const int M = N << 1;
const int pri[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 41, 43, 47};
int n, p, m;
int cnt, head[N], Next[M], v[M];
vector<int> g[20];
void read(int &x) { scanf("%d", &x); }
void Add(long long &x, long long y) {
  x += y;
  while (x >= p) x -= p;
  while (x < 0) x += p;
}
void Add(int &x, int y) {
  x += y;
  while (x >= p) x -= p;
  while (x < 0) x += p;
}
void add(int x, int y) {
  Next[++cnt] = head[x];
  head[x] = cnt;
  v[cnt] = y;
}
long long h[20];
int sz[20], pre[20], ff[20];
int ch[20][20], ss[20];
void predfs(int x, int fa) {
  h[x] = sz[x] = 1;
  ff[x] = fa;
  map<long long, int> mp;
  ss[x] = 0;
  for (int i = (0); i < (g[x].size()); i++)
    if (g[x][i] != fa) {
      int tmp = g[x][i];
      ch[x][ss[x]++] = tmp;
      predfs(tmp, x);
      sz[x] += sz[tmp];
      h[x] += pri[sz[tmp]] * h[tmp];
      if (mp.count(h[tmp]))
        pre[tmp] = mp[h[tmp]];
      else
        pre[tmp] = -1;
      mp[h[tmp]] = ss[x] - 1;
    }
}
int dp[N][13];
int f[1 << 13];
void dfs(int x, int fa) {
  for (int i = head[x]; i; i = Next[i])
    if (v[i] != fa) dfs(v[i], x);
  for (int o = (1); o <= (m); o++) {
    int all = ss[o];
    all = (1 << all) - 1;
    for (int i = (0); i <= (all); i++) f[i] = 0;
    f[0] = 1;
    for (int uu = head[x]; uu; uu = Next[uu]) {
      int tmp = v[uu];
      if (tmp == fa) continue;
      for (int mask = (all); mask >= (0); mask--)
        for (int i = (0); i < (ss[o]); i++)
          if (!(mask & (1 << i)) &&
              (pre[ch[o][i]] == -1 || (mask & (1 << pre[ch[o][i]])))) {
            Add(f[mask | (1 << i)], 1LL * f[mask] * dp[tmp][ch[o][i]] % p);
          }
    }
    dp[x][o] = f[all];
  }
}
map<long long, int> mp;
int ans;
void solve(int rt) {
  pre[rt] = -1;
  predfs(rt, 0);
  if (mp[h[rt]]) return;
  mp[h[rt]] = 1;
  memset(dp, 0, sizeof 0);
  dfs(1, 0);
  for (int i = (1); i <= (n); i++) Add(ans, dp[i][rt]);
}
int main() {
  read(n);
  int x, y;
  for (int i = (2); i <= (n); i++) {
    read(x);
    read(y);
    add(x, y);
    add(y, x);
  }
  read(m);
  for (int i = (2); i <= (m); i++) {
    read(x);
    read(y);
    g[x].push_back(y);
    g[y].push_back(x);
  }
  p = 1e9 + 7;
  for (int i = (1); i <= (m); i++) solve(i);
  cout << ans << endl;
  return 0;
}