Даны два дерева (связных неориентированных графа без циклов) 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).
Выходные данные
На единственной строке выведите одно целое число — ответ на задачу по модулю 109 + 7.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2
2 3
3 4
4 5
3
1 2
2 3
|
3
|
|
2
|
3
2 3
3 1
3
1 2
1 3
|
1
|
|
3
|
7
1 2
1 3
1 4
1 5
1 6
1 7
4
4 1
4 2
4 3
|
20
|
|
4
|
5
1 2
2 3
3 4
4 5
4
4 1
4 2
4 3
|
0
|