配点 : $1200$ 点

問題文

$0$ 以上 $M$ 以下の整数からなる長さ $N$ の広義単調増加列 $A=(A_1,A_2,\ldots,A_N)$ のうち、以下を満たすものの個数を $998244353$ で割ったあまりを各 $K=0,1,\ldots,\mathrm{MOD}-1$ に対して求めてください。

• $A$ の要素の総和を $\mathrm{MOD}$ で割ったあまりが $K$ に等しい。

制約

• $1 \leq N ,M\leq 10^6$
• $1\leq \mathrm{MOD}\leq 500$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

各 $K=0,1,\ldots,\mathrm{MOD}-1$ に対して、条件を満たす数列の個数を $998244353$ で割ったあまりを出力せよ。

2 2 4

2 1 2 1

$0$ 以上 $2$ 以下の整数からなる長さ $2$ の広義単調増加列は $(0, 0), (0, 1),(0,2), (1,1),(1,2),(2,2)$ の $6$ 通りです。

• 総和を $4$ で割ったあまりが $0$ のもの：$(0,0),(2,2)$ の $2$ 通り
• 総和を $4$ で割ったあまりが $1$ のもの：$(0,1)$ の $1$ 通り
• 総和を $4$ で割ったあまりが $2$ のもの：$(0,2),(1,1)$ の $2$ 通り
• 総和を $4$ で割ったあまりが $3$ のもの：$(1,2)$ の $1$ 通り

です。

3 45 3

5776 5760 5760

1000000 1000000 6

340418986 783857865 191848859 783857865 340418986 635287738

$998244353$ で割ったあまりを答えてください。