Score : $500$ points

问题描述

考虑在 $N$ 行和 $M$ 列的棋盘上放置 $B$ 只黑棋车和 $W$ 只白棋车。

满足以下所有条件的棋车放置被称为 良好放置。

• 将 $B+W$ 只棋车全部放置在棋盘上。
• 每个格子最多放置一只棋车。
• 没有黑白棋车互相攻击的对。即，不存在一对白棋车和黑棋车，使得它们中的一只可以通过一步移动到达另一只所在的位置。

此处，一步移动中，棋车可以到达从其当前位置出发，且在同一行或同一列上、不跳过其他棋车可达的任何格子。

有多少种不同的良好放置方式？由于这个数量可能非常巨大，请输出该数除以 $998244353$ 后的余数。

同色棋车之间不作区分。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 10:25:54