Connected Permutations
Tag(s):

## Algorithms, Combinatorics, FFT, Hard, generating-functions

Problem
Editorial
Analytics

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.$

SAMPLE INPUT
3

SAMPLE OUTPUT
1
1
3

Explanation

(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.

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

March Clash '17

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Math > Basic Math
• Algorithms > Graphs
• Data Structures > Advanced Data Structures