D. Деревянная ложка
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

$$$2^n$$$ человек, пронумерованных различными целыми числами от $$$1$$$ до $$$2^n$$$, играют в турнире по олимпийской системе. Сетка турнира представляет собой полное бинарное дерево высоты $$$n$$$ с $$$2^n$$$ листьями.

Когда два игрока сходятся в матче, всегда выигрывает тот игрок, который имеет меньший номер. Победителем турнира становится игрок, выигравший все $$$n$$$ своих матчей.

Виртуальный утешительный приз «Деревянная ложка» вручается тому игроку, который удовлетворяет следующим $$$n$$$ условиям:

  • он проиграл первый же свой матч;
  • игрок, обыгравший его, проиграл свой следующий, второй матч;
  • игрок, обыгравший этого игрока, проиграл свой третий матч;
  • $$$\ldots$$$;
  • игрок, обыгравший игрока из предыдущего пункта, проиграл финальный матч турнира.

Можно показать, что этим условиям всегда удовлетворяет ровно один игрок.

Рассмотрим все возможные $$$(2^n)!$$$ расстановок игроков в сетке турнира. Для каждого игрока найдите, в скольких из этих расстановок он получит «Деревянную ложку», и выведите эти числа по модулю $$$998\,244\,353$$$.

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

В единственной строке задано одно целое $$$n$$$ ($$$1 \le n \le 20$$$) — размер турнира.

В задаче $$$20$$$ тестов: в первом тесте $$$n = 1$$$, во втором тесте $$$n = 2$$$, $$$\ldots$$$, в $$$20$$$-м тесте $$$n = 20$$$.

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

Выведите $$$2^n$$$ целых чисел — число расстановок, при которых «Деревянную ложку» получает игрок номер $$$1, 2, \ldots, 2^n$$$, по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
1
Выходные данные
0
2
Входные данные
2
Выходные данные
0
0
8
16
Входные данные
3
Выходные данные
0
0
0
1536
4224
7680
11520
15360
Примечание

В первом примере «Деревянную ложку» всегда получает игрок $$$2$$$.

Во втором примере в $$$8$$$ расстановках игроки $$$1$$$ и $$$4$$$ встречаются друг с другом в первом матче, и тогда «Деревянную ложку» получает игрок номер $$$3$$$. В остальных $$$16$$$ расстановках приз уходит игроку номер $$$4$$$.