Consider that you are given a permutation $p$ of length $n$.
Let us define $parts(p)$ as the minimum size of a subset of $\{1, 2, 3, ..., n\}$ like $s$ that for all $i\ (1 \le i \le n)$, at least one of $i$ or $p_i$ or $p_{p_i}$ or $p_{p_{p_i}}$or ... are in $s$.
For example, $parts(1, 2, 3) = 3$ and $parts(2, 1, 3) = 2$.

ِYou are given $n$ for all $i\ (1 \le i \le n)$ find number of permutations like $p$ that $parts(p) = i$ modular $998244353$.

Input format

The only line of input contains an integer $n$.

$1 \le n \le 5 \times 10^5$

Output format

Print a single line $n$ space-separated integers denoting the answer of the problem.