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 2
using namespace std;
const int maxn = 3E3 + 5;
int tot, n, m;
long long int mod;
struct edge {
  int to, next;
};
map<unsigned long long, int> num;
map<int, vector<pair<int, int> > > what;
short to[8005][8005], sizeTree[8005];
vector<int> have[maxn];
int ans, f[maxn][8005], wait[8005];
unsigned long long S, sum[maxn], state[8005];
unsigned long long base[maxn] = {
    1,    13,   17,   19,   23,   29,   31,   37,   41,   47,   53,   59,
    61,   73,   233,  239,  241,  251,  257,  263,  269,  271,  277,  281,
    1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163,
    1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249,
    1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321,
    1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439,
    1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493};
struct hashTree {
  int size, head[maxn];
  edge E[maxn * 2];
  void clear() {
    for (int i = 1; i <= 12; ++i) head[i] = 0;
    size = 0;
  }
  inline void add(int u, int v) {
    E[++size].to = v;
    E[size].next = head[u];
    head[u] = size;
  }
  unsigned long long dfsUnordered(int u, int F) {
    sum[u] = 1;
    unsigned long long now = 0, S = 1;
    for (int i = head[u]; i; i = E[i].next) {
      int v = E[i].to;
      if (v == F) continue;
      S *= dfsUnordered(v, u);
      now ^= sum[v];
      sum[u] += sum[v];
    }
    S *= base[now];
    return S;
  }
  unsigned long long dfsRooted(int u, int F, int dep) {
    sum[u] = 1;
    unsigned long long now = 0, S = 1;
    for (int i = head[u]; i; i = E[i].next) {
      int v = E[i].to;
      if (v == F) continue;
      S += dfsRooted(v, u, dep + 1) * base[sum[v]];
      sum[u] += sum[v];
    }
    return S * sum[u];
  }
} T;
inline void out(int x) {
  for (int i = 0; i < what[x].size(); ++i)
    cout << what[x][i].first << " " << what[x][i].second << endl;
  cout << endl;
}
struct tree {
  int size, head[maxn];
  edge E[maxn * 2];
  inline void add(int u, int v) {
    E[++size].to = v;
    E[size].next = head[u];
    head[u] = size;
  }
  void calc(int u, int F) {
    f[u][1] = 1;
    have[u].push_back(1);
    for (int i = head[u]; i; i = E[i].next) {
      int v = E[i].to;
      if (v == F) continue;
      calc(v, u);
      for (int k = 0; k < have[u].size(); ++k)
        wait[have[u][k]] = f[u][have[u][k]];
      for (int j = 0; j < have[u].size(); ++j) {
        int x = have[u][j];
        if (sizeTree[x] == m) continue;
        for (int k = 0; k < have[v].size(); ++k) {
          int y = have[v][k];
          if (sizeTree[x] + sizeTree[y] > m) continue;
          if (f[u][x]) {
            if (sizeTree[x] + sizeTree[y] == m) {
              if (state[to[x][y]] == S)
                ans = (ans + (long long int)f[u][x] * (long long int)f[v][y]) %
                      mod;
            } else
              wait[to[x][y]] = (wait[to[x][y]] + (long long int)f[u][x] *
                                                     (long long int)f[v][y]) %
                               mod;
          }
        }
      }
      have[u].clear();
      for (int k = 1; k <= tot; ++k)
        if (wait[k]) {
          f[u][k] = wait[k];
          have[u].push_back(k);
          wait[k] = 0;
        }
    }
    for (int i = 0; i < have[u].size(); ++i) {
      int x = have[u][i];
      if (state[x] == S) ans = (ans + f[u][x]) % mod;
    }
  }
} G;
unsigned long long getRooted(vector<pair<int, int> > A) {
  T.clear();
  for (int i = 0; i < A.size(); ++i) {
    T.add(A[i].first, A[i].second);
    T.add(A[i].second, A[i].first);
  }
  unsigned long long sum = 0;
  return T.dfsRooted(1, 1, 0) * (A.size() + 1);
}
unsigned long long getUnordered(vector<pair<int, int> > A) {
  T.clear();
  for (int i = 0; i < A.size(); ++i) {
    T.add(A[i].first, A[i].second);
    T.add(A[i].second, A[i].first);
  }
  unsigned long long sum = 0;
  for (int i = 1; i <= A.size() + 1; ++i) sum += T.dfsUnordered(i, i);
  return sum;
}
void init() {
  vector<vector<pair<int, int> > > T, wait;
  vector<pair<int, int> > G;
  T.push_back(G);
  num[getRooted(G)] = ++tot;
  what[tot] = G;
  sizeTree[tot] = 1;
  for (int e = 2; e <= 12; ++e) {
    map<unsigned long long, bool> vis;
    for (int i = 0; i < T.size(); ++i) {
      vector<pair<int, int> > A = T[i];
      for (int u = 1; u <= e - 1; ++u) {
        A.push_back((pair<int, int>){u, e});
        unsigned long long S = getRooted(A);
        if (!vis[S]) {
          wait.push_back(A);
          vis[S] = 1;
          assert(num[S] == 0);
          num[S] = ++tot;
          what[tot] = A;
          sizeTree[tot] = e;
        }
        A.pop_back();
      }
    }
    swap(T, wait);
    wait.clear();
  }
  for (int i = 1; i <= tot; ++i)
    for (int j = 1; j <= tot; ++j)
      if (sizeTree[i] + sizeTree[j] <= 12) {
        vector<pair<int, int> > A = what[i], B = what[j], C;
        for (int k = 0; k < A.size(); ++k) C.push_back(A[k]);
        for (int k = 0; k < B.size(); ++k)
          C.push_back((pair<int, int>){B[k].first + sizeTree[i],
                                       B[k].second + sizeTree[i]});
        C.push_back((pair<int, int>){1, sizeTree[i] + 1});
        to[i][j] = num[getRooted(C)];
      } else
        break;
  for (int i = 1; i <= tot; ++i) state[i] = getUnordered(what[i]);
}
int main() {
  ios::sync_with_stdio(false);
  init();
  cin >> n;
  for (int i = 2; i <= n; ++i) {
    int x, y;
    cin >> x >> y;
    G.add(x, y);
    G.add(y, x);
  }
  cin >> m;
  vector<pair<int, int> > A;
  for (int i = 2; i <= m; ++i) {
    int x, y;
    cin >> x >> y;
    A.push_back((pair<int, int>){x, y});
  }
  mod = 1000000007;
  S = getUnordered(A);
  G.calc(1, 1);
  cout << ans << endl;
  return 0;
}