给定一个正整数 $N$。对于 $n = 1, 2, \dots, N$，请解决以下问题：

求出通过重排 $(1, 2, \dots, N)$ 得到的排列 $P = (P_1, P_2, \dots, P_N)$ 的数量（对 $998244353$ 取模），使得对于所有 $m = 1, 2, \dots, N$，满足： * $n \neq m \implies nP_n < mP_m$。

输入格式

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

$N$

• $1 \leq N \leq 5 \times 10^5$
• 所有输入值均为整数。

输出格式

输出 $N$ 行。第 $i$ 行输出当 $n = i$ 时的答案。

样例

样例输入 1

3

样例输出 1

3
1
0

说明

• 当 $n = 1$ 时，满足条件的排列为 $P = (1, 2, 3), (1, 3, 2)$ 和 $(2, 3, 1)$，总数为 $3$。
• 当 $n = 2$ 时，满足条件的排列为 $P = (3, 1, 2)$，总数为 $1$。
• 当 $n = 3$ 时，不存在满足条件的排列。