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.\)
3
1 1 3
(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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor