F. Вложение дерева
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны два дерева (связных неориентированных графа без циклов) 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