Stirling Numbers of the First Kind

Given an integer \(n\), compute the unsigned Stirling numbers of the first kind \(\begin{bmatrix} n \\ i \end{bmatrix}\) for all integers \(i\) in the range \([0, n]\). The Stirling number \(\begin{bmatrix} n \\ m \end{bmatrix}\) represents the number of ways to arrange \(n\) distinct elements into \(m\) circular permutations.

Note that by convention, \(\begin{bmatrix} 0 \\ 0 \end{bmatrix} = 1\), and when \(n > 0\) we have \(\begin{bmatrix} n \\ 0 \end{bmatrix} = 0\).

Since the answers can be extremely large, output each answer modulo 167772161 (which is \(2^{25}\times5+1\) and is prime).

The recurrence relation for \(n \ge 1\) and \(1 \le m \le n\) is:

\[ \begin{bmatrix} n \\ m \end{bmatrix} = \begin{bmatrix} n-1 \\ m-1 \end{bmatrix} + (n-1) \begin{bmatrix} n-1 \\ m \end{bmatrix} \]

inputFormat

The input consists of a single integer \(n\) where \(0 \le n\).

outputFormat

Output \(n+1\) integers separated by spaces: \(\begin{bmatrix} n \\ 0 \end{bmatrix}\), \(\begin{bmatrix} n \\ 1 \end{bmatrix}\), ..., \(\begin{bmatrix} n \\ n \end{bmatrix}\) computed modulo 167772161.

sample

0

1