Background

Tester’s note: The program running time is greatly affected by judging load, and it may be slowed down during peak times.

Problem Description

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

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

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

Input Format

One line with two positive integers $n, k$, as described above.

Output Format

One line with $n+1$ non-negative integers.

You need to output, in order, the values of $\begin{Bmatrix} 0 \\k \end{Bmatrix}, \begin{Bmatrix} 1 \\k \end{Bmatrix}, \begin{Bmatrix} 2 \\k \end{Bmatrix}, \dots, \begin{Bmatrix} n \\k \end{Bmatrix}$.

3 2

0 0 1 3

Hint

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

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

Translated by ChatGPT 5