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 10<sup class="upper-index">9</sup> + 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*<sup class="upper-index"> - 1</sup>(*A*) and *f*<sup class="upper-index"> - 1</sup>(*B*) in tree *G*.
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 *u*<sub class="lower-index">*i*</sub> and *v*<sub class="lower-index">*i*</sub> (1 ≤ *u*<sub class="lower-index">*i*</sub>, *v*<sub class="lower-index">*i*</sub> ≤ |*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 *x*<sub class="lower-index">*i*</sub> and *y*<sub class="lower-index">*i*</sub> (1 ≤ *x*<sub class="lower-index">*i*</sub>, *y*<sub class="lower-index">*i*</sub> ≤ |*T*|) and describe edges of tree *T*.
none
5
1 2
2 3
3 4
4 5
3
1 2
2 3
3
3
2 3
3 1
3
1 2
1 3
1
7
1 2
1 3
1 4
1 5
1 6
1 7
4
4 1
4 2
4 3
20
5
1 2
2 3
3 4
4 5
4
4 1
4 2
4 3
0
1
1
1
20
11 15
2 12
5 6
3 18
3 4
1 12
15 8
20 7
14 5
8 12
13 18
10 18
16 19
20 9
13 17
8 16
5 17
15 13
9 15
3
2 1
3 1
26
20
19 1
1 12
18 5
4 11
1 2
5 16
20 12
15 6
6 16
19 7
19 14
2 13
20 8
7 5
1 3
12 4
17 4
1 10
9 12
4
1 3
2 4
4 1
40
20
12 9
15 8
18 7
9 3
20 6
6 15
5 12
2 14
1 4
18 19
12 18
13 16
10 9
17 1
8 12
14 11
18 14
10 13
1 5
12
6 10
1 6
2 9
11 9
7 3
4 10
9 6
8 9
6 7
12 6
5 6
0
20
2 6
4 8
12 11
16 2
1 20
15 19
20 14
7 2
7 13
7 19
20 9
6 5
12 7
14 10
3 12
17 18
17 4
10 4
4 16
4
3 1
4 1
1 2
11
20
19 18
11 4
17 4
7 6
14 18
5 6
10 3
12 20
13 16
11 2
6 1
12 6
18 5
8 6
17 6
13 17
20 9
15 13
10 11
3
2 1
3 1
32
20
14 17
20 7
13 15
20 4
18 9
6 3
16 13
5 20
6 14
13 11
6 20
2 20
4 19
20 13
12 13
2 9
2 8
10 1
6 10
2
1 2
19
20
9 19
20 10
15 5
1 4
2 5
3 13
20 2
17 12
16 6
2 3
19 15
3 14
15 11
8 7
18 12
2 17
2 1
8 5
18 16
11
6 4
1 2
5 11
8 3
7 3
3 5
4 2
10 2
3 2
9 6
0
20
9 13
2 7
11 15
2 3
15 14
11 12
8 2
19 8
6 9
7 16
12 1
20 4
13 18
20 2
10 14
13 7
8 15
17 4
8 5
5
3 2
4 2
4 1
4 5
46
20
14 19
19 15
7 17
19 8
9 16
12 16
10 11
13 7
15 13
2 1
13 2
6 15
9 18
9 3
20 19
10 9
13 16
4 13
12 5
10
8 7
5 6
2 3
7 6
1 9
9 6
3 8
10 3
2 4
6
20
12 14
3 19
6 9
7 8
18 1
13 3
1 4
16 18
15 10
17 16
2 5
19 5
20 4
19 7
12 18
19 12
14 15
11 2
7 9
9
3 4
6 7
5 9
2 5
5 7
7 8
7 1
4 8
6
30
4 26
26 16
11 4
17 29
12 15
14 30
2 1
8 9
21 20
25 24
17 6
10 13
29 24
3 26
18 25
14 25
17 7
4 25
12 10
20 10
25 23
26 10
28 13
19 20
4 5
13 27
22 18
5 9
10 1
2
2 1
29
40
15 11
7 2
6 8
40 27
13 39
5 26
8 25
14 30
36 19
13 38
17 3
8 33
4 2
1 40
17 5
11 1
24 33
4 8
10 31
26 32
38 26
10 18
23 32
1 16
33 5
12 6
6 14
17 28
9 8
22 21
36 15
16 35
32 37
36 22
17 36
20 21
6 34
4 31
11 29
1
40
50
33 44
14 10
26 25
29 24
21 15
13 7
16 26
29 17
16 44
49 9
35 42
28 38
37 20
10 12
48 2
21 47
46 40
46 31
42 8
31 45
38 11
4 19
3 35
22 39
41 9
11 6
34 44
37 44
22 41
33 35
41 4
22 1
13 27
13 22
14 33
18 21
36 22
21 31
30 35
31 43
24 12
44 32
27 2
41 21
1 50
23 19
6 22
14 41
47 5
3
3 1
3 2
85
60
35 24
14 29
40 57
16 56
16 35
9 58
35 50
17 45
9 45
57 18
40 60
19 54
33 50
16 6
32 57
10 17
20 35
55 27
60 11
30 19
27 36
12 41
33 44
50 12
19 20
52 12
51 40
17 47
52 42
39 13
13 5
22 58
59 37
44 34
43 42
36 7
23 59
45 49
4 53
26 19
17 35
39 16
20 48
59 6
38 13
31 5
10 3
40 29
8 18
46 43
50 36
1 35
4 15
4 57
12 28
9 21
58 32
10 2
4 25
2
2 1
59
70
22 52
54 23
67 70
3 31
8 40
68 10
33 27
60 61
50 13
57 6
34 66
29 48
29 9
28 44
6 12
32 10
7 30
26 21
12 13
54 34
14 49
12 40
7 18
43 44
58 41
14 25
53 10
56 65
30 49
38 55
57 4
30 15
54 63
17 38
68 7
34 3
46 17
13 44
20 49
40 34
33 7
2 66
36 57
35 18
30 12
11 22
68 22
67 9
19 57
65 13
62 6
49 51
42 27
61 20
6 1
30 24
12 17
25 39
46 37
14 5
68 41
6 64
12 45
69 61
7 26
59 16
12 16
40 67
47 3
1
70
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph(n, m):
    x, s = [0] * (2 * m), [0] * (n + 3)
    for i in range(0, 2 * m, 2):
        u, v = map(int, input().split())
        s[u + 2] += 1
        s[v + 2] += 1
        x[i], x[i + 1] = u, v
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * (2 * m)
    for i in range(2 * m):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return G, s

def bfs(G, s0, s):
    q, k = list(s), 0
    dist = [inf] * (n + 1)
    for i in q:
        dist[i] = 0
    parent = [-1] * (n + 1)
    while len(q) ^ k:
        i = q[k]
        di = dist[i]
        for v in range(s0[i], s0[i + 1]):
            j = G[v]
            if dist[j] == inf:
                q.append(j)
                dist[j] = di + 1
                parent[j] = i
        k += 1
    return q, dist, parent

def f(u, v):
    return u * (n + 1) + v

def g(S, s0, n):
    y = [0] * (m + 1)
    d = dict()
    for i in range(1, n + 1):
        for v in range(s0[i], s0[i + 1]):
            j = S[v]
            d[(i, j)] = v
    for i in q[::-1][:-len(s)]:
        if not child[i]:
            for j in range(2 * (n - 1)):
                dp[f(i, j)] = 1
            continue
        c = child[i]
        z = len(c)
        for j in range(z):
            y[c[j]] = j
        for u in range(1, n + 1):
            if s0[u + 1] - s0[u] <= z:
                continue
            dp0 = [0] * pow2[z]
            dp0[0] = 1
            dpl, dpr = [list(dp0)], [list(dp0)]
            for w in range(s0[u], s0[u + 1]):
                v = S[w]
                x = d[(v, u)]
                dp1 = list(dp0)
                for j in range(pow2[z]):
                    if not dp0[j]:
                        continue
                    dpj = dp0[j]
                    for k in range(z):
                        if j & pow2[k]:
                            continue
                        l = j ^ pow2[k]
                        dp1[l] += dpj * dp[f(c[k], x)] % mod
                        dp1[l] %= mod
                dp0 = dp1
                dpl.append(list(dp0))
            dp0 = [0] * pow2[z]
            dp0[0] = 1
            for w in range(s0[u + 1] - 1, s0[u] - 1, -1):
                v = S[w]
                x = d[(v, u)]
                dp1 = list(dp0)
                for j in range(pow2[z]):
                    if not dp0[j]:
                        continue
                    dpj = dp0[j]
                    for k in range(z):
                        if j & pow2[k]:
                            continue
                        l = j ^ pow2[k]
                        dp1[l] += dpj * dp[f(c[k], x)] % mod
                        dp1[l] %= mod
                dp0 = dp1
                dpr.append(list(dp0))
            dpr.reverse()
            for w in range(s0[u], s0[u + 1]):
                v = S[w]
                dp1, dp2 = dpl[w - s0[u]], dpr[w - s0[u] + 1]
                j = f(i, w)
                for k, l in zip(dp1, dp2[::-1]):
                    dp[j] += k * l % mod
                dp[j] %= mod
    ans = 0
    if len(s) == 1:
        c = child[q[0]]
        z = len(c)
        for u in range(1, n + 1):
            if s0[u + 1] - s0[u] < z:
                continue
            dp0 = [0] * pow2[z]
            dp0[0] = 1
            for w in range(s0[u], s0[u + 1]):
                v = S[w]
                x = d[(v, u)]
                dp1 = list(dp0)
                for j in range(pow2[z]):
                    if not dp0[j]:
                        continue
                    dpj = dp0[j]
                    for k in range(z):
                        if j & pow2[k]:
                            continue
                        l = j ^ pow2[k]
                        dp1[l] += dpj * dp[f(c[k], x)] % mod
                        dp1[l] %= mod
                dp0 = dp1
            ans += dp0[-1]
    else:
        c1, c2 = child[q[0]], child[q[1]]
        z1, z2 = len(c1), len(c2)
        for u1 in range(1, n + 1):
            if s0[u1 + 1] - s0[u1] < z1:
                continue
            for w0 in range(s0[u1], s0[u1 + 1]):
                u2 = S[w0]
                if s0[u2 + 1] - s0[u2] < z2:
                    continue
                p = 1
                for u, c, z in [(u1, c1, z1), (u2, c2, z2)]:
                    dp0 = [0] * pow2[z]
                    dp0[0] = 1
                    for w in range(s0[u], s0[u + 1]):
                        v = S[w]
                        if v == u1 or v == u2:
                            continue
                        x = d[(v, u)]
                        dp1 = list(dp0)
                        for j in range(pow2[z]):
                            if not dp0[j]:
                                continue
                            dpj = dp0[j]
                            for k in range(z):
                                if j & pow2[k]:
                                    continue
                                l = j ^ pow2[k]
                                dp1[l] += dpj * dp[f(c[k], x)] % mod
                                dp1[l] %= mod
                        dp0 = dp1
                    p *= dp0[-1]
                    if not p:
                        break
                ans += p % mod
    return ans % mod

n = int(input())
S, s0 = make_graph(n, n - 1)
m = int(input())
T, t0 = make_graph(m, m - 1)
mod = pow(10, 9) + 7
if m <= 2:
    ans = n if m == 1 else 2 * (n - 1)
    print(ans)
    exit()
inf = pow(10, 9) + 1
q, _, _ = bfs(T, t0, [1])
q, dist, parent = bfs(T, t0, [q[-1]])
c = q[-1]
d = dist[c]
for _ in range(d // 2):
    c = parent[c]
s = [c, parent[c]] if d % 2 else [c]
q, dist, parent = bfs(T, t0, s)
child = [[] for _ in range(m + 1)]
for i in range(1, m + 1):
    if parent[i] ^ -1:
        child[parent[i]].append(i)
l = 2 * (n - 1) * (m + 1)
dp = [0] * l
pow2 = [1]
for _ in range(m):
    pow2.append(2 * pow2[-1])
ans = g(S, s0, n) * pow(g(T, t0, m), mod - 2, mod) % mod
print(ans)