← 返回题目列表

Codeforces · 762/F

F. 树嵌套

中文机器翻译题面 查看原题

给你两棵树(连通无向无环图)S 和 T。

计算 S 中与树 T 同构的子树(连通子图)的数量。由于这个数字可能会变得很大,因此输出它对 109 + 7 取模。

如果 S 中存在恰好属于其中一棵的顶点,则树 S 的两棵子树被认为是不同的。

如果存在从 G 的顶点集到 H 的顶点集的双射 f,并且具有以下属性,则树 G 被称为与树 H 同构:如果树 G 中的顶点 A 和 B 之间存在边,则树 H 中的顶点 f(A) 和 f(B) 之间一定存在边。反之亦然 — 如果树中的顶点 A 和 B 之间存在边H,树G中f - 1(A)和f - 1(B)之间必须有边。

输入

第一行包含一个整数 |S| (1 ≤ |S| ≤ 1000) — 树 S 的顶点数。

下一个 |S| - 1 行包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ |S|) 并描述树 S 的边。

下一行包含一个整数 |T| (1 ≤ |T| ≤ 12) — 树 T 的顶点数。

下一个 |T| - 1 行包含两个整数 xi 和 yi (1 ≤ xi, yi ≤ |T|) 并描述树 T 的边。

输出

在第一行输出一个整数——给定任务的答案模 109 + 7。

示例

输入 #1

5
1 2
2 3
3 4
4 5
3
1 2
2 3

输出 #1

3

输入 #2

3
2 3
3 1
3
1 2
1 3

输出 #2

1

输入 #3

7
1 2
1 3
1 4
1 5
1 6
1 7
4
4 1
4 2
4 3

输出 #3

20

输入#4

5
1 2
2 3
3 4
4 5
4
4 1
4 2
4 3

输出#4

0