P5409 Stirling Numbers of the First Kind · Sequence

This is a template problem, with no background. **Checker’s note: The program running time is greatly affected by judging load, and it may get time-limited during peak judging periods.**

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

One line with two positive integers $n, k$, as described in the statement.

One line with $n+1$ non-negative integers. 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}$.

For $20\%$ of the testdata, $n \leqslant 1000$. For $100\%$ of the testdata, $1 \leqslant k, n < 131072$. Translated by ChatGPT 5