Compute Stirling Numbers of the Second Kind

Given a nonnegative integer n, compute the number of ways to partition a set of n distinct elements into i nonempty, indistinguishable subsets. This number is given by the second kind Stirling number $$\begin{Bmatrix} n \\ i \end{Bmatrix}$$ for all integers i such that 0 ≤ i ≤ n.

Note that for n > 0, we define $$\begin{Bmatrix} n \\ 0 \end{Bmatrix}=0,$$ and also by convention $$\begin{Bmatrix} 0 \\ 0 \end{Bmatrix}=1.$$

Because the answer can be very large, output all answers modulo 167772161 (which is a prime number, equal to 2²⁵×5+1).

inputFormat

The input consists of a single integer n (with n ≥ 0).

outputFormat

Output n+1 space-separated integers representing $$\begin{Bmatrix} n \\ 0 \end{Bmatrix},\;\begin{Bmatrix} n \\ 1 \end{Bmatrix},\;\dots,\;\begin{Bmatrix} n \\ n \end{Bmatrix}$$ all taken modulo 167772161.

sample

0

1