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 = 1020, M = 15;
const int Mod = 1000000007;
int n, m, t1, t2, Head1[N], Head2[N];
int g[1 << M], p[1 << M], ans;
map<int, vector<int> > List;
map<int, int> f[N];
struct edge {
  int ver, next;
} e1[N * 2], e2[N * 2];
void insert(int x, int y, int id) {
  if (id == 1)
    e1[++t1] = (edge){y, Head1[x]}, Head1[x] = t1,
    e1[++t1] = (edge){x, Head1[y]}, Head1[y] = t1;
  if (id == 2)
    e2[++t2] = (edge){y, Head2[x]}, Head2[x] = t2,
    e2[++t2] = (edge){x, Head2[y]}, Head2[y] = t2;
}
void input() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    insert(u, v, 1);
  }
  scanf("%d", &m);
  for (int i = 1; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    insert(u, v, 2);
  }
}
int lenth(int x) { return 32 - __builtin_clz(x); }
void connect(int &x, int y) { x = x << lenth(y) | y; }
int Ergodic(int x, int fa) {
  int S = 1;
  vector<int> cur;
  for (int i = Head2[x]; i; i = e2[i].next) {
    int y = e2[i].ver;
    if (y == fa) continue;
    cur.push_back(Ergodic(y, x));
  }
  sort(cur.begin(), cur.end());
  vector<int>::iterator it;
  for (it = cur.begin(); it != cur.end(); it++) connect(S, *it);
  S <<= 1;
  if (!List.count(S)) List[S] = cur;
  return S;
}
void dp(int x, int fa) {
  vector<int> ch;
  for (int i = Head1[x]; i; i = e1[i].next) {
    int y = e1[i].ver;
    if (y == fa) continue;
    ch.push_back(y);
    dp(y, x);
  }
  map<int, vector<int> >::iterator it;
  for (it = List.begin(); it != List.end(); it++) {
    vector<int> cur = it->second;
    int S = it->first, len = cur.size();
    memset(g, 0, sizeof(g));
    g[0] = 1;
    for (int i = 0; i < ch.size(); i++) {
      memcpy(p, g, sizeof(g));
      for (int j = 0; j < len; j++) {
        int val = f[ch[i]][cur[j]];
        if (val == 0) continue;
        for (int k = (1 << len) - 1; k >= 0; k--)
          if (g[k] && !(k >> j & 1) &&
              (j == 0 || cur[j] != cur[j - 1] || (k >> (j - 1) & 1)))
            p[k | (1 << j)] = (p[k | (1 << j)] + 1LL * g[k] * val % Mod) % Mod;
      }
      memcpy(g, p, sizeof(p));
    }
    if (g[(1 << len) - 1]) {
      f[x][S] = g[(1 << len) - 1];
      if (lenth(S) == (m << 1)) ans = (ans + f[x][S]) % Mod;
    }
  }
}
int main() {
  input();
  for (int i = 1; i <= m; i++) Ergodic(i, 0);
  dp(1, 0);
  printf("%d\n", ans);
}