\(2^n\) человек, пронумерованных различными целыми числами от \(1\) до \(2^n\), играют в турнире по олимпийской системе. Сетка турнира представляет собой полное бинарное дерево высоты \(n\) с \(2^n\) листьями.
Когда два игрока сходятся в матче, всегда выигрывает тот игрок, который имеет меньший номер. Победителем турнира становится игрок, выигравший все \(n\) своих матчей.
Виртуальный утешительный приз «Деревянная ложка» вручается тому игроку, который удовлетворяет следующим \(n\) условиям:
- он проиграл первый же свой матч;
- игрок, обыгравший его, проиграл свой следующий, второй матч;
- игрок, обыгравший этого игрока, проиграл свой третий матч;
- \(\ldots\);
- игрок, обыгравший игрока из предыдущего пункта, проиграл финальный матч турнира.
Можно показать, что этим условиям всегда удовлетворяет ровно один игрок.
Рассмотрим все возможные \((2^n)!\) расстановок игроков в сетке турнира. Для каждого игрока найдите, в скольких из этих расстановок он получит «Деревянную ложку», и выведите эти числа по модулю \(998\,244\,353\).
Выходные данные
Выведите \(2^n\) целых чисел — число расстановок, при которых «Деревянную ложку» получает игрок номер \(1, 2, \ldots, 2^n\), по модулю \(998\,244\,353\).
Примечание
В первом примере «Деревянную ложку» всегда получает игрок \(2\).
Во втором примере в \(8\) расстановках игроки \(1\) и \(4\) встречаются друг с другом в первом матче, и тогда «Деревянную ложку» получает игрок номер \(3\). В остальных \(16\) расстановках приз уходит игроку номер \(4\).