SOLVE
LATER
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.\)
(1) is connected permutation.
(2, 1) is connected permutation, (1, 2) is not.
(2, 3, 1), (3, 1, 2), (3, 2, 1) are connected permutations, (1, 2, 3), (1, 3, 2), (2, 1, 3) are not.