Connected Permutations
問題
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.\)
実行速度: 5
メモリ制限: 256
ソース制限:
説明
(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.
