AT_arc171_e.[ARC171E] Rookhopper's Tour

有一个纵向 $N$ 格、横向 $N$ 格的网格。网格中从上往下第 $i$ 行、从左往右第 $j$ 列的格子记作 $(i,\,j)$。此外，有 $1$ 个黑子和 $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$ 取模的结果。

输入为以下格式，从标准输入读入。

$N$ $M$ $A$ $B$

输出能够获胜的白子放置方案数对 $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$ 均为整数

样例说明 1

例如，将白子按如下方式放置：

......
..BW..
.....W
......
..W...
....W.

此时，你可以按以下步骤移动黑子并获胜：

• 移除 $(5,\,3)$ 的白子，将黑子移到 $(6,\,3)$。
• 移除 $(6,\,5)$ 的白子，将黑子移到 $(6,\,6)$。
• 移除 $(3,\,6)$ 的白子，将黑子移到 $(2,\,6)$。
• 移除 $(2,\,4)$ 的白子，将黑子移到 $(2,\,3)$。
• 此时所有白子都被移除，且黑子回到 $(A,\,B) = (2,\,3)$，你获胜。

能够获胜的白子放置方案共有 $4$ 种。

由 ChatGPT 4.1 翻译