$$$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
1
输出 #1
0 2
输入 #2
2
输出 #2
0 0 8 16
输入 #3
3
输出 #3
0 0 0 1536 4224 7680 11520 15360
注意
在第一个示例中,“木勺”始终奖励给玩家 $$$2$$$。
在第二个示例中,有 $$$8$$$ 安排,玩家 $$$1$$$ 和 $$$4$$$ 在第一场比赛中相遇,在这些情况下,“木勺”被授予玩家 $$$3$$$。在剩余的 $$$16$$$ 安排中,“木勺”被授予玩家 $$$4$$$。