{"raw_statement":[{"iden":"statement","content":"You are given two trees (connected undirected acyclic graphs) _S_ and _T_.\n\nCount 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.\n\nTwo subtrees of tree _S_ are considered different, if there exists a vertex in _S_ that belongs to exactly one of them.\n\nTree _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_."},{"iden":"input","content":"The first line contains a single integer |_S_| (1 ≤ |_S_| ≤ 1000) — the number of vertices of tree _S_.\n\nNext |_S_| - 1 lines contain two integers _u__i_ and _v__i_ (1 ≤ _u__i_, _v__i_ ≤ |_S_|) and describe edges of tree _S_.\n\nThe next line contains a single integer |_T_| (1 ≤ |_T_| ≤ 12) — the number of vertices of tree _T_.\n\nNext |_T_| - 1 lines contain two integers _x__i_ and _y__i_ (1 ≤ _x__i_, _y__i_ ≤ |_T_|) and describe edges of tree _T_."},{"iden":"output","content":"On the first line output a single integer — the answer to the given task modulo 109 + 7."},{"iden":"examples","content":"Input\n\n5\n1 2\n2 3\n3 4\n4 5\n3\n1 2\n2 3\n\nOutput\n\n3\n\nInput\n\n3\n2 3\n3 1\n3\n1 2\n1 3\n\nOutput\n\n1\n\nInput\n\n7\n1 2\n1 3\n1 4\n1 5\n1 6\n1 7\n4\n4 1\n4 2\n4 3\n\nOutput\n\n20\n\nInput\n\n5\n1 2\n2 3\n3 4\n4 5\n4\n4 1\n4 2\n4 3\n\nOutput\n\n0"}],"translated_statement":[{"iden":"statement","content":"给定两棵树（连通无向无环图）#cf_span[S] 和 #cf_span[T]。\n\n计算树 #cf_span[S] 中与树 #cf_span[T] 同构的子树（连通子图）的数量。由于这个数可能很大，请输出其对 #cf_span[109 + 7] 取模的结果。\n\n树 #cf_span[S] 的两个子树被认为是不同的，当且仅当存在一个顶点属于其中一个子树但不属于另一个。\n\n树 #cf_span[G] 被称为与树 #cf_span[H] 同构，当且仅当存在一个双射 #cf_span[f]，将 #cf_span[G] 的顶点集映射到 #cf_span[H] 的顶点集，满足以下性质：如果在树 #cf_span[G] 中顶点 #cf_span[A] 和 #cf_span[B] 之间有边，则在树 #cf_span[H] 中顶点 #cf_span[f(A)] 和 #cf_span[f(B)] 之间也必须有边；反之，如果在树 #cf_span[H] 中顶点 #cf_span[A] 和 #cf_span[B] 之间有边，则在树 #cf_span[G] 中顶点 #cf_span[f - 1(A)] 和 #cf_span[f - 1(B)] 之间也必须有边。\n\n第一行包含一个整数 #cf_span[|S|]（#cf_span[1 ≤ |S| ≤ 1000]）——树 #cf_span[S] 的顶点数。\n\n接下来 #cf_span[|S| - 1] 行，每行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ |S|]），描述树 #cf_span[S] 的边。\n\n下一行包含一个整数 #cf_span[|T|]（#cf_span[1 ≤ |T| ≤ 12]）——树 #cf_span[T] 的顶点数。\n\n接下来 #cf_span[|T| - 1] 行，每行包含两个整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi, yi ≤ |T|]），描述树 #cf_span[T] 的边。\n\n第一行输出一个整数——该任务的答案对 #cf_span[109 + 7] 取模的结果。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[|S|]（#cf_span[1 ≤ |S| ≤ 1000]）——树 #cf_span[S] 的顶点数。接下来 #cf_span[|S| - 1] 行，每行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ |S|]），描述树 #cf_span[S] 的边。下一行包含一个整数 #cf_span[|T|]（#cf_span[1 ≤ |T| ≤ 12]）——树 #cf_span[T] 的顶点数。接下来 #cf_span[|T| - 1] 行，每行包含两个整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi, yi ≤ |T|]），描述树 #cf_span[T] 的边。"},{"iden":"output","content":"第一行输出一个整数——该任务的答案对 #cf_span[109 + 7] 取模的结果。"},{"iden":"examples","content":"输入\n5\n1 2\n2 3\n3 4\n4 5\n3\n1 2\n2 3\n输出\n3\n\n输入\n3\n2 3\n3 1\n3\n1 2\n1 3\n输出\n1\n\n输入\n7\n1 2\n1 3\n1 4\n1 5\n1 6\n1 7\n4\n4 1\n4 2\n4 3\n输出\n20\n\n输入\n5\n1 2\n2 3\n3 4\n4 5\n4\n4 1\n4 2\n4 3\n输出\n0"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ S = (V_S, E_S) $ be a tree with $ |V_S| = n $, $ n \\leq 1000 $.  \nLet $ T = (V_T, E_T) $ be a tree with $ |V_T| = m $, $ m \\leq 12 $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 1000 $  \n2. $ 1 \\leq m \\leq 12 $  \n3. $ S $ and $ T $ are connected, undirected, and acyclic.  \n\n**Objective**  \nCount the number of subtrees $ S' = (V', E') $ of $ S $ (i.e., connected, acyclic subgraphs of $ S $) such that $ S' \\cong T $, i.e., there exists a bijection $ f: V' \\to V_T $ satisfying:  \n$$\n\\{u, v\\} \\in E' \\iff \\{f(u), f(v)\\} \\in E_T\n$$  \nOutput the count modulo $ 10^9 + 7 $.  \n\nTwo subtrees are distinct if their vertex sets differ.","simple_statement":null,"has_page_source":false}