Score : $1200$ points

Problem Statement

Find the number, modulo $998244353$, of non-decreasing sequences $A=(A_1,A_2,\ldots,A_N)$ of length $N$ consisting of integers between $0$ and $M$ (inclusive) that satisfy the following, for each $K=0,1,\ldots,\mathrm{MOD}-1$:

• the sum of the elements in $A$ is congruent to $K$ modulo $\mathrm{MOD}$.

Constraints

• $1 \leq N ,M\leq 10^6$
• $1\leq \mathrm{MOD}\leq 500$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$ $\mathrm{MOD}$

Output

For each $K=0,1,\ldots,\mathrm{MOD}-1$, print the number, modulo $998244353$, of sequences that satisfy the condition.

2 2 4

2 1 2 1

There are $6$ non-decreasing sequences of length $2$ consisting of integers between $0$ and $2$: $(0, 0), (0, 1),(0,2), (1,1),(1,2),(2,2)$. Here, we have:

• $2$ sequences whose sums are congruent to $0$ modulo $4$: $(0,0),(2,2)$;
• $1$ sequence whose sum is congruent to $1$ modulo $4$: $(0,1)$;
• $2$ sequences whose sums are congruent to $2$ modulo $4$: $(0,2),(1,1)$;
• $1$ sequence whose sum is congruent to $3$ modulo $4$: $(1,2)$.

3 45 3

5776 5760 5760

1000000 1000000 6

340418986 783857865 191848859 783857865 340418986 635287738

Print the counts modulo $998244353$.