Открывая тайную дверь, раскрой нескончаемый переменчивый сказочный мир.

Назовем миром неориентированный граф 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) оказались в разных компонентах связности.

Найдите число непохожих миров, которые могли получиться, по модулю 10⁹ + 7. Два мира называются похожими, если они изоморфны и есть изоморфизм, который не переобозначает вершины s и t. Формально, два мира G и H считаются похожими, если между их множествами вершин существует биекция такая, что:

• f(s(G)) = s(H);
• f(t(G)) = t(H);
• Две вершины u и v в графе G соседние в G, если и только если f(u) и f(v) соседние в H.