CF762F Tree nesting

给定两棵树（连通无环无向图）$S$ 和 $T$。 请统计树 $S$ 中有多少个子树（连通子图）与树 $T$ 同构。由于答案可能很大，请输出其对 $10^{9}+7$ 取模后的值。 如果树 $S$ 中存在某个顶点仅属于某一个子树，则这两个子树被认为是不同的。 树 $G$ 被称为与树 $H$ 同构，是指存在一个从 $G$ 的顶点集合到 $H$ 的顶射 $f$，且满足如下条件：若 $G$ 中的顶点 $A$ 与 $B$ 有一条边，则 $H$ 中 $f(A)$ 与 $f(B)$ 必有一条边。反之亦然——如果 $H$ 中 $A$ 与 $B$ 有一条边，则 $G$ 中 $f^{-1}(A)$ 与 $f^{-1}(B)$ 必有一条边。

第一行包含一个整数 $|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$ 的一条边。

第一行输出一个整数，表示所求方案数对 $10^{9}+7$ 取模的结果。

由 ChatGPT 5 翻译