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;
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int &x, int y, int mod = 1000000007) {
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et() {
  puts("-1");
  exit(0);
}
int ans;
int len(int x) { return 32 - __builtin_clz(x); }
void jin(int &x, int y) { x = (x << len(y)) | y; }
unordered_map<int, int> num[1005];
int f[2][1 << 12];
struct mb {
  vector<int> mp[1005];
  int n;
  map<int, vector<int>> idm;
  void rd() {
    scanf("%d", &n);
    for (int i = 0, u, v; i < n - 1; i++) {
      scanf("%d%d", &u, &v);
      mp[u].push_back(v);
      mp[v].push_back(u);
    };
  }
  int dfs(int x, int pa) {
    vector<int> tmp;
    for (int c : mp[x])
      if (c != pa) tmp.push_back(dfs(c, x));
    sort(tmp.begin(), tmp.end());
    int res = 1;
    for (int z : tmp) jin(res, z);
    res <<= 1;
    if (idm.find(res) == idm.end()) idm[res] = tmp;
    return res;
  }
  void cal() {
    for (int(i) = 1; (i) <= (int)(n); (i)++) dfs(i, 0);
  }
  void wk(int x, int pa, mb &T) {
    for (int c : mp[x])
      if (c != pa) wk(c, x, T);
    for (auto &pi : T.idm) {
      auto &V = pi.second;
      int id = pi.first, N = V.size();
      int tt = 0;
      for (int(j) = 0; (j) < (int)(1 << N); (j)++) f[0][j] = f[1][j] = 0;
      f[0][0] = 1;
      for (int c : mp[x])
        if (c != pa) {
          int pre = tt, cur = tt ^ 1;
          tt ^= 1;
          for (int(j) = 0; (j) < (int)(1 << N); (j)++) f[cur][j] = f[pre][j];
          for (int(i) = 0; (i) < (int)(N); (i)++) {
            if (num[c][V[i]]) {
              for (int j = (1 << N) - 1; ~j; j--) {
                if (f[pre][j] && !((1 << i) & j) &&
                    !(i && V[i] == V[i - 1] && !((1 << (i - 1)) & j))) {
                  addmod(f[cur][j | (1 << i)],
                         (long long)num[c][V[i]] * f[pre][j] % 1000000007);
                }
              }
            }
          }
        }
      if (f[tt][(1 << N) - 1]) {
        num[x][id] = f[tt][(1 << N) - 1];
        if (len(id) == 2 * T.n) {
          addmod(ans, f[tt][(1 << N) - 1]);
        }
      }
    }
  }
} s, t;
void fmain(int tid) {
  s.rd();
  t.rd();
  t.cal();
  s.wk(1, 0, t);
  printf("%d\n", ans);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}