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.