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

Сообщается, что конференция 2050 пройдет в городе Юньци в Ханчжоу с 23 по 25 апреля. На ней будут тематические форумы, утренние пробежки, походы, и так далее.

Отношения между $$$n$$$ волонтерами конференции 2050 могут быть представлены как дерево (связный неориентированный граф с $$$n$$$ вершинами и $$$n-1$$$ ребром). $$$n$$$ вершин дерева соответствуют $$$n$$$ волонтерам и пронумерованы $$$1,2,\ldots, n$$$.

Определим расстояние между двумя волонтерами $$$i$$$ и $$$j$$$, dis$$$(i,j)$$$, как количество ребер на кратчайшем пути из вершины $$$i$$$ в вершину $$$j$$$ в дереве. dis$$$(i,j)=0$$$, если $$$i=j$$$.

Некоторые волонтеры смогут принять участие в очном воссоединении, а некоторые — нет. Если для некоторого волонтера $$$x$$$ и неотрицательного целого числа $$$r$$$, все волонтеры, чье расстояние до $$$x$$$ не больше $$$r$$$, смогут принять участие в очном воссоединении, то форум с радиусом $$$r$$$ может состояться. Уровень очного воссоединения определяется как максимальный возможный радиус форума, который может состояться.

Предположим, что каждый волонтер сможет принять участие в воссоединении с вероятностью $$$\frac{1}{2}$$$, и все эти события независимы. Найдите математическое ожидание уровня очного воссоединения. Если ни один волонтер не сможет принять участие, уровень равен $$$-1$$$. Если все волонтеры смогут принять участие, уровень равен $$$n$$$.

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

Первая строка содержит одно целое число $$$n$$$ ($$$2\le n\le 300$$$), обозначающее количество волонтеров.

Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$a$$$ и $$$b$$$, обозначающих ребро между вершинами $$$a$$$ и $$$b$$$.

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

Выведите математическое ожидание уровня очного воссоединения по модулю $$$998\,244\,353$$$.

Формально, пусть $$$M = 998\,244\,353$$$. Можно показать, что ответ может быть представлен как несократимая вещественная дробь $$$\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}$$$.

Примеры
Входные данные
3
1 2
2 3
Выходные данные
499122177
Входные данные
5
1 2
2 3
3 4
3 5
Выходные данные
249561089
Входные данные
10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
Выходные данные
821796866
Примечание

В первом примере следующая таблица показывает возможные варианты. $$$yes$$$ означает, что волонтер сможет принять участие, а $$$no$$$ — что не сможет. $$$$$$\begin{array}{cccc} 1 & 2 & 3 & level\\ yes & yes & yes & 3\\ yes & yes & no & 1\\ yes & no & yes & 0\\ yes & no & no & 0\\ no & yes & yes & 1\\ no & yes & no & 0\\ no & no & yes & 0\\ no & no & no & -1\\ \end{array}$$$$$$ Математическое ожидание уровня равно $$$\frac{3+1+1+(-1)}{2^3}=\frac{1}{2}$$$.