问题描述

Kuro和Shiro正在玩一个由$n$个方块组成的排列在一行上的棋盘。方块从左到右编号为$1$到$n$，第$s$个方块上有一个标记。

首先，对于每个方块，Kuro以相等的概率独立地将其涂成黑色或白色，然后他在方块$s$上放置与方块相同颜色的石头。

Kuro和Shiro将使用这个棋盘以及无限多的黑色石头和白色石头来玩一个游戏。在这个游戏中，Kuro和Shiro交替放置石头，具体规则如下，Kuro先开始：

1. 选择一个与已经放有石头的方块相邻的空方块。假设选择了方块$i$。
2. 在方块$i$上放置与该方块相同颜色的石头。
3. 如果除了方块$i$之外还有其他包含与刚刚放置的石头颜色相同的石头的方块，则在这些方块中，选择与方块$i$最近的方块$j$。将方块$i$和方块$j$之间的所有石头的颜色改为方块$i$的颜色。

当棋盘上没有空方块时，游戏结束。

Kuro会以最优策略玩游戏，以使游戏结束时黑石的数量最大，而Shiro会以最优策略玩游戏，以使游戏结束时白石的数量最大。

对于每种情况$s=1,\\dots,n$，找出在游戏结束时黑石数量的期望值，对$998244353$取模。

注意事项

当所求的期望值可以表示为既约分数$p/q$时，一定存在一个整数$r$，满足$rq=p ~(\\text{mod } 998244353)$且$0 \\leq r \\lt 998244353$，要求你找出$r$的值。

约束条件

• $1 \\leq n \\leq 2\\times 10^5$

输入

输入以以下格式从标准输入给出:

$n$

输出

输出$n$个值。第$i$个值应为在$s=i$的情况下，黑石数量的期望值对$998244353$取模。

示例输入1

3

示例输出1

499122178
499122178
499122178

让我们用b表示黑色方块，用w表示白色方块。有八种可能的棋盘状态：www、wwb、wbw、wbb、bww、bwb、bbw和bbb，它们被等概率地选择。

对于这些棋盘的每一种情况，无论$s$的值如何，游戏结束时都会有$0$、$1$、$0$、$2$、$1$、$3$、$2$和$3$个黑石。因此，石头的期望数量为$(0+1+0+2+1+3+2+3)/8 = 3/2$，答案是$r = 499122178$，满足$2r = 3 ~(\\text{mod } 998244353)$且$0 \\leq r \\lt 998244353$。

示例输入2

10

示例输出2

5
5
992395270
953401350
735035398
735035398
953401350
992395270
5
5

示例输入3

19

示例输出3

499122186
499122186
499110762
499034602
498608106
496414698
485691370
434999274
201035754
138645483
201035754
434999274
485691370
496414698
498608106
499034602
499110762
499122186
499122186