F. Tree nestingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputThe first line contains a single integer |S| (1 ≤ |S| ≤ 1000) — the number of vertices of tree S.Next |S| - 1 lines contain two integers ui and vi (1 ≤ ui, vi ≤ |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 xi and yi (1 ≤ xi, yi ≤ |T|) and describe edges of tree T.OutputOn the first line output a single integer — the answer to the given task modulo 109 + 7.ExamplesInput51 22 33 44 531 22 3Output3Input32 33 131 21 3Output1Input71 21 31 41 51 61 744 14 24 3Output20Input51 22 33 44 544 14 24 3Output0
Input51 22 33 44 531 22 3
Output3
['combinatorics', 'graphs', 'trees', '*2800']