如果一个整数区间满足以下条件，则称其为“线段树型”区间：

• 该区间可以表示为 $[2^i j, 2^i (j + 1))$，其中 $0 \le i \le K$，$0 \le j < 2^{K-i}$，且 $i, j$ 为整数。

对于满足 $0 \le l < r \le 2^K$ 的整数对 $(l, r)$，可以证明区间 $[l, r)$ 总能表示为若干个线段树型区间的并。我们将所需的最小区间数量记为 $f(l, r)$。

对于 $k = 1, 2, \dots, 2^K - 2$，解决以下问题：

• 求满足 $f(l, r) = k$ 的整数对 $(l, r)$ ($0 \le l < r \le 2^K$) 的数量，结果对 $998244353$ 取模。

输入格式

输入通过标准输入给出，格式如下：

$K$

• $K$ 是一个整数。
• $2 \le K \le 5 \times 10^5$

输出格式

按顺序输出 $k = 1, 2, \dots, 2^K - 2$ 时对应问题的答案。

样例

样例输入 1

3

样例输出 1

15 14 6 1

样例输入 2

5

样例输出 2

63 110 132 114 70 30 8 1

样例输入 3

10

样例输出 3

2047 4975 10896 21772 38360 58724 77184 86312 81448 64324 42112 22576 9744 3304 848 155 18 1

说明

在第一个样例中，当 $k = 4$ 时，仅当 $l = 1, r = 7$ 时满足 $f(l, r) = k$，因此输出为 $1$。