102482: [AtCoder]ABC248 C - Dice Sum

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

问题描述

有多少长度为$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$

输出

打印答案。

样例输入1

2 3 4

样例输出1

6

以下六个序列满足条件。

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

样例输入2

31 41 592

样例输出2

798416518

确保打印的结果模$998244353$。