NPM998244353 (Hard)

길이가 $N$인 정수 중에서 $P$로 나누어떨어지고 각 자리 숫자의 합이 $M$ 이하인 것이 몇 개인지 세려고 한다. 맨 앞자리가 0이어도 되므로, 0부터 9까지의 숫자를 $N$개 나열한 것은 모두 길이가 $N$인 정수로 본다. 예를 들어 $N = 2$일 때 00과 03도 각각 하나로 센다.

$M = 0, 1, \dots, MM$ 각각에 대해 조건을 만족하는 수의 개수를 998244353으로 나눈 나머지를 구하는 프로그램을 작성하시오.

첫째 줄에 $N$, $P$, $MM$이 공백으로 구분되어 주어진다. ($1 \le N \le 10^9$, $1 \le P \le 16$, $1 \le MM \le 15000$)

첫째 줄에 정수 $MM+1$개를 공백 한 칸으로 구분해 출력한다. 앞에서부터 $i$번째 정수($i = 0, 1, \dots, MM$)는 $M = i$일 때의 정답, 즉 길이가 $N$인 정수 중에서 $P$로 나누어떨어지고 각 자리 숫자의 합이 $i$ 이하인 것의 개수를 998244353으로 나눈 나머지이다.

$N = 2$, $P = 3$인 경우 세는 수는 다음과 같다.

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

$N = 2$, $P = 4$인 경우는 다음과 같다.

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