C - Dice Sum Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の整数からなる数列 A=(A_1,\ldots,A_N) であって、以下の条件を全て満たすものは何通りありますか？

  • 1\le A_i \le M (1 \le i \le N)

  • \displaystyle\sum _{i=1}^N A_i \leq K

ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割った余りを求めてください。

制約

  • 1 \leq N, M \leq 50
  • N \leq K \leq NM
  • 入力は全て整数

入力

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

N M K

出力

答えを 998244353 で割った余りを出力せよ。

入力例 1

2 3 4

出力例 1

6

条件を満たす数列は以下の 6 つです。

  • (1,1)
  • (1,2)
  • (1,3)
  • (2,1)
  • (2,2)
  • (3,1)

入力例 2

31 41 592

出力例 2

798416518

答えを 998244353 で割った余りを出力してください。

Score : 300 points

Problem Statement

How many integer sequences of length N, A=(A_1, \ldots, A_N), satisfy all of the conditions below?

  • 1\le A_i \le M (1 \le i \le N)

  • \displaystyle\sum _{i=1}^N A_i \leq K

Since the count can get enormous, find it modulo 998244353.

Constraints

  • 1 \leq N, M \leq 50
  • N \leq K \leq NM
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M K

Output

Print the answer.

Sample Input 1

2 3 4

Sample Output 1

6

The following six sequences satisfy the conditions.

  • (1,1)
  • (1,2)
  • (1,3)
  • (2,1)
  • (2,2)
  • (3,1)

Sample Input 2

31 41 592

Sample Output 2

798416518

Be sure to print the count modulo 998244353.