D - Coincidence 解説 /

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

配点 : 100

問題文

長さ N の整数列の組 A=(A_1, A_2, \dots, A_N), B=(B_1, B_2, \dots, B_N) があります.最初は全ての i = 1, 2, \dots, N に対して A_i=B_i=0 です.

あなたは A, B に対して次の操作を M 回行います.

  • 操作:整数 i, j\ (1 \le i, j \le N) を選び, A_iB_j の値を 1 ずつ増やす.

ただし, M 回の操作のうち i=j であるのはちょうど X 回である必要があります.

M 回の操作後の A, B の組としてありうるものの個数を 998244353 で割った余りを求めてください.

制約

  • 2 \leq N \leq 3000
  • 0 \leq X \leq M \le 3000
  • 入力は全て整数

入力

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

N \ M \ X

出力

M 回の操作後の A, B の組としてありうるものの個数を 998244353 で割った余りを出力せよ.


入力例 1

3 1 1

出力例 1

3

次の 3 個です.

  • A=(1,0,0), \ B=(1,0,0)
  • A=(0,1,0), \ B=(0,1,0)
  • A=(0,0,1), \ B=(0,0,1)

入力例 2

3 1 0

出力例 2

6

次の 6 個です.

  • A=(1,0,0), \ B=(0,1,0)
  • A=(1,0,0), \ B=(0,0,1)
  • A=(0,1,0), \ B=(1,0,0)
  • A=(0,1,0), \ B=(0,0,1)
  • A=(0,0,1), \ B=(1,0,0)
  • A=(0,0,1), \ B=(0,1,0)

入力例 3

4 4 2

出力例 3

643

例えば次のような A, B の組がありえます.

  • A=(1,1,1,1), \ B=(1,1,1,1)
  • A=(1,0,0,3), \ B=(0,1,0,3)

入力例 4

314 1592 653

出力例 4

755768689

Score : 100 points

Problem Statement

You have a pair of integer sequences A=(A_1, A_2, \dots, A_N), B=(B_1, B_2, \dots, B_N). Initially A_i=B_i=0 holds for all i = 1, 2, \dots, N.

You will perform the following operation M times.

  • Operation: Choose two integers i, j\ (1 \le i, j \le N) and increment A_i and B_j by 1.

Here, out of the M operations, the number of operations in which i=j holds must be exactly X.

Find the number, modulo 998244353, of pairs of integer sequences that A, B can be after the M operations.

Constraints

  • 2 \leq N \leq 3000
  • 0 \leq X \leq M \le 3000
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N \ M \ X

Output

Print the number, modulo 998244353, of pairs of integer sequences that A, B can be after the M operations.


Sample Input 1

3 1 1

Sample Output 1

3

The following 3 pairs are possible.

  • A=(1,0,0), \ B=(1,0,0)
  • A=(0,1,0), \ B=(0,1,0)
  • A=(0,0,1), \ B=(0,0,1)

Sample Input 2

3 1 0

Sample Output 2

6

The following 6 pairs are possible.

  • A=(1,0,0), \ B=(0,1,0)
  • A=(1,0,0), \ B=(0,0,1)
  • A=(0,1,0), \ B=(1,0,0)
  • A=(0,1,0), \ B=(0,0,1)
  • A=(0,0,1), \ B=(1,0,0)
  • A=(0,0,1), \ B=(0,1,0)

Sample Input 3

4 4 2

Sample Output 3

643

The followings are examples of possible pairs.

  • A=(1,1,1,1), \ B=(1,1,1,1)
  • A=(1,0,0,3), \ B=(0,1,0,3)

Sample Input 4

314 1592 653

Sample Output 4

755768689