Олимпиадный тренинг

Задача . B. Древесный массив

Задача

Темы: графы Деревья дп Комбинаторика математика Перебор Теория вероятностей *2300

Вам задано дерево, состоящее из $n$ вершин. По заданному дереву вы строите массив, отмечая вершины по одной.

Первоначально, когда еще не помечено ни одной вершины, вы выбираете вершину равновероятно по всем вершинам дерева и отмечаете ее.

После этого, пока еще остаются непомеченные вершины, вы выбираете и помечаете вершину равновероятно среди всех еще непомеченных, но связанных по ребру хотя бы с одной помеченной вершиной.

Можно доказать, что данный процесс пометит все вершины в дереве.

Финальный массив $a$ — это список номеров вершин в порядке, в котором они были помечены.

Определите математическое ожидание количества инверсий в массиве, полученном на основе заданного дереве с помощью описанного выше алгоритма.

Количество инверсий в массиве $a$ — это количество пар индексов $(i, j)$ таких, что $i < j$ и $a_i > a_j$. Например, в массиве $[4, 1, 3, 2]$ количество инверсий равно $4$: $(1, 2)$, $(1, 3)$, $(1, 4)$, $(3, 4)$.

Входные данные

В первой строке задано одно целое число $n$ ($2 \le n \le 200$) — количество вершин в дереве.

В следующих $n - 1$ строках заданы по два целых числа $x$ и $y$ ($1 \le x, y \le n$; $x \neq y$), означающие ребро между вершинами $x$ и $y$.

Гарантируется, что заданные ребра образуют дерево.

Выходные данные

Выведите математическое ожидание количества инверсий в построенном массиве по модулю $10^9+7$.

Формально, пусть $M = 10^9+7$. Можно показать, что ответ может быть представлен в виде несократимой дроби $\frac{p}{q}$, где $p$ и $q$ — целые числа, и $q \not \equiv 0 \pmod{M}$. Выведите целое число, равное $p \cdot q^{-1} \bmod M$. Другими словами, выведите такое целое число $x$, что $0 \le x < M$ и $x \cdot q \equiv p \pmod{M}$.

Примечание

Изображение дерева из первого примера:

$\text{[math]}$

В первом примере получающиеся массивы почти фиксированы. Если первоначально выбрана вершина $2$, то единственный возможный массив — это $[2, 1, 3]$ ($1$ инверсия). Если первоначально выбрана вершина $3$, то единственный возможный массив — это $[3, 1, 2]$ ($2$ инверсии). Если первоначально выбрана вершина $1$, то массивы $[1, 2, 3]$ ($0$ инверсий) и $[1, 3, 2]$ ($1$ инверсия) — это единственные варианты и они равновероятны. В результате математическое ожидание количества инверсий равно $\frac{1}{3}\cdot 1 + \frac{1}{3} \cdot 2 + \frac{1}{3} \cdot (\frac{1}{2} \cdot 0 + \frac{1}{2} \cdot 1) = \frac{7}{6}$.