题目描述

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

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

広義単調増加列とは ある数列 $B$ について、 $B$ の長さを $|B|$ としたとき、全ての整数 $i$ ($1\ \le\ i\ \le\ |B|\ -\ 1$) について、 $B_i\ \leq\ B_{i+1}$ が成り立つとき、またそのときに限って、 $B$ は広義単調増加列です。

输入格式

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

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

输出格式

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

题目大意

• 对于每个 $0\le k<mod$ 的整数 $k$，求出长度为 $n$，值域为 $[0,m]$ 且满足 $\sum_{i=1}^na_i\equiv k\pmod{mod}$ 的序列 $a$ 的个数。$a$ 是单调不减序列。

• $1\le n,m\le10^6$，$1\le mod\le500$，答案对 $998244353$ 取模。

2 2 4

2 1 2 1

3 45 3

5776 5760 5760

1000000 1000000 6

340418986 783857865 191848859 783857865 340418986 635287738

提示

制約

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

Sample Explanation 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$ 通り です。

Sample Explanation 3

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