分数: 800 点
问题陈述
有一个网格 N 行和 N 列。让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。另外,还有一颗黑石和 M 白色石头。
您将使用这些物品玩单人游戏。
这是规则。最初,您将黑石放在 (A, B)。然后,您将每个 M 网格的某些单元格上有白色石头。这里:
- 你不能将白子放在 (A, B).
- 每行最多可以放置一颗白石。
- 每列最多可以放置一颗白石。
然后,您将执行以下操作,直到无法执行为止:
- 假设黑子位于 (i, j)。执行以下四种操作之一:
- 如果在 (i, k) 其中 (j < k),移走白棋并将黑棋移动到 (i, k + 1).
- 如果在 (i, k) 其中 (j > k),移走白棋并将黑棋移动到 (i, k - 1).
- 如果在 (k, j) 其中 (i < k),移走白棋并将黑棋移动到 (k + 1, j).
- 如果在 (k, j) 其中 (i > k),移走白棋并将黑棋移动到 (k - 1, j).
- 这里,如果黑子要移动到的单元格不存在,则不能进行这样的移动。
下图说明了一个示例。在这里, B 代表黑色石头, W 代表白色的石头, . 代表一个空单元格,并且 O 代表黑石可以移动到的单元格。
..O... ..W... ...... ...... ..B.WO ......
完成操作后,如果满足以下所有条件,您就赢得了游戏。否则,你就输了。
- 所有白色棋子已从网格中移除。
- 黑石放置在 (A, B).
有多少个初始配置 M 白子你能通过最佳执行操作赢得比赛吗?求计数模数 998244353.
约束
- 2 \leq M \leq N \leq 2 \times 10^5
- 1 \leq A \leq N
- 1 \leq B \leq N
- N, M, A,和 B 是整数。
输入
输入由标准输入按以下格式给出:
N M A B
输出
打印数字,模数 998244353,可以为您带来胜利的白石的可能配置。
样本输入 1
6 4 2 3
示例输出 1
4
例如,考虑如下图所示放置的白棋:
...... ..BW.. .....W ...... ..W... ....W.
在这里,您可以通过以下步骤移动黑子来赢得游戏:
- 移除位于 (5, 3) 并将黑石移至 (6, 3).
- 移除位于 (6, 5) 并将黑石移至 (6, 6).
- 移除位于 (3, 6) 并将黑石移至 (2, 6).
- 移除位于 (2, 4) 并将黑石移至 (2, 3).
- 由于所有白棋都已从网格中移除,而黑棋被放置在 (A, B) = (2, 3),你赢得了比赛。
有四种白石配置可以帮助您取得胜利。
示例输入 2
5 3 1 3
示例输出 2
0
示例输入 3
200000 47718 21994 98917
示例输出 3
146958602