/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
縦 N 行、横 M 列のマス目に、黒い飛車の駒 B 個と白い飛車の駒 W 個を設置することを考えましょう。
以下の条件をすべて満たす設置の仕方を いい配置 と呼びます。
- B+W 個の駒すべてが設置されている。
- 1 つのマスに置かれている駒の数は高々 1 つである。
- ある白い駒と黒い駒の組であって、互いが互いを攻撃しているようなものが存在しない。すなわち、ある白い駒と黒い駒の組であって、一方が 1 手の移動によってもう片方が置かれているマスに到達できるようなものが存在しない。
ここで、飛車の駒は、今いる位置から上、下、右、左のいずれかの方向に伸びる直線上にあり、かつ他の駒を飛び越えずに到達できるマスに 1 手で移動することができます。
いい配置としてあり得るものは何通りありますか？答えは非常に大きくなることがあるので、998244353 で割ったあまりを出力してください。
同じ色の駒同士は区別しないものとします。
制約
- 1 \leq N,M \leq 50
- 1 \leq B,W \leq 2500
- B+W \leq N \times M
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M B W
出力
答えを 998244353 で割ったあまりを出力せよ。
入力例 1
2 2 1 1
出力例 1
4
いい配置としてあり得るものは以下の 4 通りです。
入力例 2
1 2 1 1
出力例 2
0
いい配置としてあり得るものが存在しない場合もあります。
入力例 3
40 40 30 30
出力例 3
467620384
998244353 で割ったあまりを出力することに注意してください。
Score : 500 points
Problem Statement
Consider placing B black rooks and W white rooks on a grid with N horizontal rows and M vertical columns.
A placement of the rooks satisfying all of the following conditions is called a good placement.
- All B+W rooks are placed on the grid.
- At most one rook is placed in the same square.
- There is no pair of white rook and black rook attacking each other. That is, there is no pair of white rook and black rook such that one of them can reach the square in which the other is placed in one move.
Here, in one move, a rook can reach any square that is on a horizontal or vertical line from its current position and is reachable without jumping over another rook.
How many good placements are there? Since this count can be enormous, print it modulo 998244353.
Rooks in the same color are not distinguished.
Constraints
- 1 \leq N,M \leq 50
- 1 \leq B,W \leq 2500
- B+W \leq N \times M
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M B W
Output
Print the count modulo 998244353.
Sample Input 1
2 2 1 1
Sample Output 1
4
There are four good placements as follows.
Sample Input 2
1 2 1 1
Sample Output 2
0
There may be no good placement.
Sample Input 3
40 40 30 30
Sample Output 3
467620384
Be sure to print the count modulo 998244353.