F - Modulo Sum of Increasing Sequences Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 1200 点

問題文

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 は広義単調増加列です。

制約

  • 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 で割ったあまりを出力せよ。

入力例 1

2 2 4

出力例 1

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 通り

です。

入力例 2

3 45 3

出力例 2

5776 5760 5760

入力例 3

1000000 1000000 6

出力例 3

340418986 783857865 191848859 783857865 340418986 635287738

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

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}.
What is a non-decreasing sequence? A sequence B is non-decreasing if and only if B_i \leq B_{i+1} for every integer (1 \le i \le |B| - 1), where |B| is the length of B.

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.

Sample Input 1

2 2 4

Sample Output 1

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

Sample Input 2

3 45 3

Sample Output 2

5776 5760 5760

Sample Input 3

1000000 1000000 6

Sample Output 3

340418986 783857865 191848859 783857865 340418986 635287738

Print the counts modulo 998244353.