CF762F.Tree nesting

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.

给你两棵树（连通的无向无环图）$S$ 和 $T$。

统计 $S$ 中与树 $T$ 同构的子树（连通子图）的个数。由于该数目可能非常大，请将结果对 $10^9 + 7$ 取模后输出。

若存在 $S$ 中的一个顶点，它恰好属于两个子树中的一个，则称 $S$ 的这两个子树互不相同。

若存在一个双射 $f$，其定义域为树 $G$ 的顶点集、值域为树 $H$ 的顶点集，且满足如下性质：当且仅当 $G$ 中顶点 $A$ 与 $B$ 之间有边时，$H$ 中顶点 $f(A)$ 与 $f(B)$ 之间也有边，则称树 $G$ 与树 $H$ 同构。换言之，若 $H$ 中顶点 $A$ 与 $B$ 之间有边，则 $G$ 中顶点 $f^{-1}(A)$ 与 $f^{-1}(B)$ 之间也必须有边。

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__i and v__i (1 ≤ u__i, v__i ≤ |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__i and y__i (1 ≤ x__i, y__i ≤ |T|) and describe edges of tree T.

第一行包含一个整数 $|S|$（$1 \leq |S| \leq 1000$）——树 $S$ 的顶点数。

接下来的 $|S|-1$ 行每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq |S|$），描述树 $S$ 的边。

下一行包含一个整数 $|T|$（$1 \leq |T| \leq 12$）——树 $T$ 的顶点数。

接下来的 $|T|-1$ 行每行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i, y_i \leq |T|$），描述树 $T$ 的边。

On the first line output a single integer — the answer to the given task modulo 109 + 7.

在第一行输出一个整数——该问题答案对 $10^9 + 7$ 取模的结果。