Description

The Stirling number of the first kind $\begin{bmatrix}n\\ m\end{bmatrix}$ represents the number of ways to arrange $n$ distinct elements into $m$ circular permutations.

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 should output the result modulo $167772161$ ($2^{25}\times 5+1$, which is a prime).

Input Format

A single line containing a positive integer $n$, as described in the statement.

Output Format

Output one line with $n+1$ non-negative integers.

You need to 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 2 3 1

Hint

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

For $100\%$ of the testdata, $1\leqslant n< 262144$.

Translated by ChatGPT 5