Сообщается, что конференция 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\).
Выходные данные
Выведите математическое ожидание уровня очного воссоединения по модулю \(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}\).
Примечание
В первом примере следующая таблица показывает возможные варианты. \(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}\).