/ 
Time Limit: 2 sec / Memory Limit: 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_i と B_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