NPM998244353 (Hard)

Time limit5sMemory limit512 MB

Summary

For every digit-sum cap from 0 to MM, count length-N digit strings divisible by P, modulo 998244353.

Level: Hard9 of 10
Topics: Combinatorics, Dynamic programming, Number theory, Matrix
Solved: No attempts yet

Problem

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.

Input

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

Output

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.

Hint

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

Examples2

Example 1
Input
```
2 3 3
```
Expected output
```
1 1 1 5
```
Example 2
Input
```
2 4 4
```
Expected output
```
1 1 2 3 5
```