We say that permutation p of size n is connected if there is no k, $1\leqslant k < n$, such that $p(1), p(2), \dots, p(k)$ is permutation of $1,2,\dots, k.$
You are given a positive integer n. Find out number of connected permutations of size $1,2,\dots,n$. As this numbers can be large, print them modulo $924844033.$

Input Format:
Single line containing integer n.

Output Format:
Output n lines, numbers of connected permutations of size $1, 2, \dots, n$.

Constraints:
$1 \leqslant n \leqslant 500,000.$

50 points
$n \leqslant 5,000.$