Открывая тайную дверь, раскрой нескончаемый переменчивый сказочный мир.
Назовем миром неориентированный граф G, во множестве вершин которого V(G) есть две особые вершины s(G) и t(G). Начальный мир имеет множество вершин {s(G), t(G)} и ребро между ними.
С начальным миром произошло n изменений. В каждом изменении была добавлена новая вершина w во множество V(G), выбрано существующее ребро (u, v), и добавлены два новых ребра (u, w) и (v, w) во множество ребер E(G). Обратите внимание, некоторые ребра могут быть выбраны в более, чем одном изменении.
Известно, что в итоговом графе минимальный s-t разрез равен m, то есть, нужно удалить хотя бы m ребер, чтобы s(G) и t(G) оказались в разных компонентах связности.
Найдите число непохожих миров, которые могли получиться, по модулю 109 + 7. Два мира называются похожими, если они изоморфны и есть изоморфизм, который не переобозначает вершины s и t. Формально, два мира G и H считаются похожими, если между их множествами вершин существует биекция 
такая, что:
- f(s(G)) = s(H);
- f(t(G)) = t(H);
- Две вершины u и v в графе G соседние в G, если и только если f(u) и f(v) соседние в H.
Примечание
В первом примере следующие 6 миров попарно непохожи и удовлетворяют всем ограничениям, s(G) обозначена зеленым, t(G) обозначена синим, один из минимальных разрезов обозначен голубым.
Во втором примере следующие 3 мира удовлетворяют ограничениям.
