Background

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

Problem Description

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$.

Input Format

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

Output Format

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

3 10

90 90 90 90 90 90 90 90 90 90

Hint

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

Translated by ChatGPT 5