Алиса находится на дне кроличьей норы! Кроличья нора может быть смоделирована как дерево\(^{\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}\).
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел в одной строке — вероятности того, что Алиса убежит, начиная с вершины \(1, 2, \ldots, n\). Поскольку эти вероятности могут быть очень малыми, выведите их по модулю \(998\,244\,353\).