C1984 [Contest #16]小 C 的 01 序列

有这样一类特殊的 $01$ 序列 $S_k$，定义如下：

• 对于 $k=0$，$S_0 = 0$。
• 对于 $k \ge 1$，$S_k$ 是在 $S_{k-1}$ 的基础上，将 $0$ 替换为 $01$，$1$ 替换为 $10$ 后得到的序列。

例如，$S_0 = 0, S_1 = 01,S_2 = 0110, S_3 = 01101001,\cdots$

给定 $n$，询问 $S_n$ 中 $00, 01, 10, 11$ 作为子串分别出现了多少次。

答案对 $998244353$ 取模。

样例输入 1

1

样例输出 1

0 1 0 0

样例输入 2

3

样例输出 2

1 3 2 1