Даны два дерева (связных неориентированных графа без циклов) S и T.
Требуется посчитать количество поддеревьев (связных подграфов) дерева S, изоморфных дереву T. Так как это число может быть достаточно большим, выведите его по модулю 109 + 7.
Два поддерева дерева S считаются различными, если хотя бы одна вершина S входит ровно в одно из этих поддеревьев.
Дерево G называется изоморфным дереву H, если существует биекция f из множества вершин дерева G в множество вершин дерева H, обладающая следующим свойством: если в дереве G есть ребро между вершинами A и B, то в дереве H должно быть ребро между вершинами f(A) и f(B), и наоборот — если в дереве H есть ребро между вершинами A и B, то в дереве 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.
5 1 2 2 3 3 4 4 5 3 1 2 2 3
3
3 2 3 3 1 3 1 2 1 3
1
7 1 2 1 3 1 4 1 5 1 6 1 7 4 4 1 4 2 4 3
20
5 1 2 2 3 3 4 4 5 4 4 1 4 2 4 3
0
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач