炸弹游戏 2

题目描述

有 $N$ 个人排成一列,第 $i$ 个人站在从前数第 $i$ 个位置。

重复以下操作,直到队伍中只剩下一个人:

以 $\frac{1}{2}$ 的概率移除队伍最前面的人,否则将他移到队伍末尾。

对每个人 $i=1,2,\ldots,N$,求第 $i$ 个人成为最后留在队伍中的人的概率,对 $998244353$ 取模。(所有移除或不移除的选择都是随机且独立的。)

输入格式

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

$N$

输出格式

对 $i=1,2,\ldots,N$,用空格分隔输出答案。

样例

2

332748118 665496236

第 1 个人成为最后留在队伍中的人的概率为 $\frac{1}{3}$。

第 2 个人成为最后留在队伍中的人的概率为 $\frac{2}{3}$。

5

235530465 792768557 258531487 238597268 471060930

数据范围

• $2\leq N\leq 3000$
• 输入中的所有值均为整数。

提示

本题所求的概率可以证明总是有理数。 另外,在该问题的约束下,当所求概率表示为不可约分数 $\frac{y}{x}$ 时,可以保证 $x$ 不被 $998244353$ 整除。

这里,存在唯一的整数 $z$,满足 $0 \le z \le 998244352$ 且 $xz \equiv y \pmod{998244353}$。输出这个 $z$。