P9006 [Intro Contest #9] Lord Divine Tree Swings the Wand (Hard Version).

**This problem has exactly the same meaning as the Easy Version, and only the constraints for $n, k$ are different.**

Lord Divine Tree swings the wand and summons $9 \times 10^{n-1}$ domesticated fairies. Each domesticated fairy has a unique $n$-digit ID number $a_i$. Lord Divine Tree wants to divide these domesticated fairies into $k$ groups. All fairies in group $p$ satisfy that their ID number $a_i$ leaves remainder $p-1$ when taken modulo $k$, that is, $a_i \equiv p-1 \pmod k$. Lord Divine Tree wants to know how many fairies are in each group. Since the answer may be very large, you only need to output the result modulo $100,000,007$.

The input consists of one line with two integers, in order $n, k$.

Output one line with $k$ integers separated by spaces. The $i$-th integer represents the number of fairies in the $i$-th group.

For $100\%$ of the testdata, $1 \le n \le 5000$, $1 \le k \le 1000$. Translated by ChatGPT 5