NPM998244353 (Hard)

Count the integers of length $N$ that are divisible by $P$ and whose digit sum is at most $M$. The leading digit may be 0, so every sequence of $N$ digits taken from 0 to 9 counts as one integer of length $N$. For $N = 2$, both 00 and 03 are counted.

For each $M = 0, 1, \dots, MM$, compute the number of such integers modulo 998244353.

The first line contains $N$, $P$, and $MM$, separated by spaces. ($1 \le N \le 10^9$, $1 \le P \le 16$, $1 \le MM \le 15000$)

Print $MM+1$ integers on the first line, separated by single spaces. The $i$-th integer ($i = 0, 1, \dots, MM$) is the answer for $M = i$: the number of integers of length $N$ that are divisible by $P$ and whose digit sum is at most $i$, modulo 998244353.

For $N = 2$ and $P = 3$ the counted numbers are:

• $M = 0, 1, 2$: 00
• $M = 3$: 00, 03, 12, 21, 30

For $N = 2$ and $P = 4$:

• $M = 0, 1$: 00
• $M = 2$: 00, 20
• $M = 3$: 00, 12, 20
• $M = 4$: 00, 04, 12, 20, 40