给你两棵树(连通无向无环图)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