← 返回题目列表

AtCoder · arc171_e

E. Rookhopper 之旅

中文机器翻译题面 查看原题

分数: 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