C - 数列 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 3 点

問題文

M 以下の非負整数からなる長さ N の整数列のうち、総和が S であるものの個数を 998244353 で割った余りを求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq S \leq 2 \times 10^5
  • N, M, S は整数

入力

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

N M S

出力

答えを出力せよ。

入力例 1

3 2 4

出力例 1

6

条件を満たす数列は次の 6 個です。

  • (0,2,2)
  • (1,1,2)
  • (1,2,1)
  • (2,0,2)
  • (2,1,1)
  • (2,2,0)

入力例 2

12345 678 90123

出力例 2

226012779

Score: 3 points

Problem Statement

Among integer sequences of length N consisting of non-negative integers not greater than M, find the number of sequences whose total sum is exactly S.
Output the result modulo 998244353.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq S \leq 2 \times 10^5
  • N, M, S are integers

Input

The input is given from standard input in the following format:

N M S

Output

Print the answer.

Sample Input 1

3 2 4

Sample Output 1

6

There are 6 sequences that satisfy the condition:

  • (0,2,2)
  • (1,1,2)
  • (1,2,1)
  • (2,0,2)
  • (2,1,1)
  • (2,2,0)

Sample Input 2

12345 678 90123

Sample Output 2

226012779