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 long long mod = 1e9 + 7;
const int maxn = 1079, maxm = 12;
int ans = 0;
int n, m;
vector<vector<int> > s(maxn), t(maxm);
map<vector<int>, int> num;
vector<vector<int> > need;
int dfs_number(int v, int p = -1) {
  vector<int> son;
  for (int i : t[v]) {
    if (i == p) continue;
    son.push_back(dfs_number(i, v));
  }
  sort(son.begin(), son.end());
  if (!num.count(son)) {
    num[son] = need.size();
    need.push_back(son);
  }
  return num[son];
}
inline void add(int& a, const int& b) {
  a += b;
  if (a >= mod) a -= mod;
}
vector<vector<int> > dp;
void dfs_dp(int v, int p = -1) {
  vector<vector<int> > cur(need.size());
  for (int i = 0; i < need.size(); i++) {
    cur[i].resize((1 << need[i].size()), 0);
    cur[i][0] = 1;
  }
  for (int i : s[v]) {
    if (i == p) continue;
    dfs_dp(i, v);
    for (int my = 0; my < need.size(); my++) {
      for (int j = (1 << need[my].size()) - 1; j >= 0; j--) {
        for (int pos = 0; pos < need[my].size(); pos++) {
          if ((j & (1 << pos)) || (pos && !(j & (1 << (pos - 1))) &&
                                   need[my][pos] == need[my][pos - 1]))
            continue;
          add(cur[my][j | (1 << pos)],
              (cur[my][j] * 1ll * dp[i][need[my][pos]]) % mod);
        }
      }
    }
  }
  for (int my = 0; my < need.size(); my++)
    add(dp[v][my], cur[my][(1 << need[my].size()) - 1]);
  add(ans, dp[v][need.size() - 1]);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 0, u, v; i < n - 1; i++) {
    cin >> u >> v;
    s[--u].push_back(--v);
    s[v].push_back(u);
  }
  cin >> m;
  for (int i = 0, u, v; i < m - 1; i++) {
    cin >> u >> v;
    t[--u].push_back(--v);
    t[v].push_back(u);
  }
  vector<int> roots;
  for (int i = 0; i < m; i++) {
    int tmp = need.size();
    dfs_number(i);
    if (tmp < need.size()) roots.push_back(i);
  }
  for (int r : roots) {
    need.clear();
    num.clear();
    dfs_number(r);
    dp.assign(n, vector<int>(need.size(), 0));
    dfs_dp(0);
  }
  cout << ans << "\n";
  return 0;
}