考虑每棵具有 $$$n$$$ 顶点的树(连通无向无环图)($$$n$$$ 为奇数,顶点编号从 $$$1$$$ 到 $$$n$$$),并且对于每个 $$$2 \le i \le n$$$,第 $$$i$$$ 个顶点恰好与索引较小的一个顶点相邻。
对于每个 $$$i$$$ ($$$1 \le i \le n$$$) 计算第 $$$i$$$ 个顶点作为质心的树的数量。答案可能很大,输出它对 $$$998\,244\,353$$$ 取模。
如果一个顶点的删除将树分割成每个最多包含 $$$(n-1)/2$$$ 个顶点的子树,则该顶点称为质心。
输入
第一行包含一个奇数整数 $$$n$$$ ($$$3 \le n < 2 \cdot 10^5$$$, $$$n$$$ 是奇数) — 树中顶点的数量。
输出
在一行中打印 $$$n$$$ 个整数,第 $$$i$$$ 个整数是第 $$$i$$$ 个顶点的答案(模 $$$998\,244\,353$$$)。
示例
输入 #1
3
输出 #1
1 1 0
输入 #2
5
输出 #2
10 10 4 0 0
输入 #3
7
输出 #3
276 276 132 36 0 0 0
注意
示例 $$$1$$$:有两种可能的树:边为 $$$(1-2)$$$ 和 $$$(1-3)$$$ — 这里的质心是 $$$1$$$;并且边为 $$$(1-2)$$$ 和 $$$(2-3)$$$ — 这里的质心是 $$$2$$$。所以答案是 $$$1, 1, 0$$$。
示例 $$$2$$$:有 $$$24$$$ 可能的树,例如边为 $$$(1-2)$$$、$$$(2-3)$$$、$$$(3-4)$$$ 和 $$$(4-5)$$$。这里的质心是$$$3$$$。