Description

The Stirling number of the second kind $\begin{Bmatrix} n \\m \end{Bmatrix}$ is the number of ways to partition $n$ distinct elements into $m$ identical non-empty sets.

Given $n$, for every integer $i \in [0,n]$, you need to compute $\begin{Bmatrix} n \\i \end{Bmatrix}$.

Since the answer can be very large, you must output the result modulo $\bm{167772161}$ ($\bm{2^{25}\times 5+1}$, which is a prime).

Input Format

A single line containing a positive integer $n$, as described above.

Output Format

A single line containing $n+1$ non-negative integers.

Output, in order, the values of $\begin{Bmatrix} n \\0 \end{Bmatrix},\begin{Bmatrix} n \\1 \end{Bmatrix},\begin{Bmatrix} n \\2 \end{Bmatrix},\dots,\begin{Bmatrix} n \\n \end{Bmatrix}$.

3

0 1 3 1

Hint

For $20\%$ of the testdata, $n \leqslant 1000$.

For $100\%$ of the testdata, $1 \leqslant n \leqslant 2\times 10^5$.

Translated by ChatGPT 5