Алиса находится на дне кроличьей норы! Кроличья нора может быть смоделирована как дерево$^{\text{∗}}$, у которого выход находится на вершине $1$, а Алиса начинает с некоторой вершины $v$. Она хочет выбраться из норы, но, к сожалению, Дама Червей приказала её казнить.

Каждую минуту подбрасывается обычная монета. Если выпадает орёл, Алиса может переместиться в любую вершину, смежную со своим текущим положением, а если решка, Дама Червей может перетащить Алису на смежную вершину по своему выбору. Если Алиса когда-либо окажется на любом из некорневых листьев$^{\text{†}}$ дерева, Алиса проигрывает.

Предполагая, что они обе действуют оптимально, для каждой начальной вершины $1\le v\le 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}$.