AtCoder Regular Contest 171
E
Rookhopper's Tour
AtCoder
⌀ 3034
原题
← DF →
翻译中…

Problem Statement

翻译中…

There is a grid with $N$ rows and $N$ columns. Let $(i, j)$ denote the cell at the $i$-th row from the top and the $j$-th column from the left. Additionally, there is one black stone and $M$ white stones. You will play a single-player game using these items.

翻译中…

Here are the rules. Initially, you place the black stone at $(A, B)$. Then, you place each of the $M$ white stones on some cell of the grid. Here:

翻译中…
  • You cannot place a white stone at $(A, B)$.
  • You can place at most one white stone per row.
  • You can place at most one white stone per column.
翻译中…

Then, you will perform the following operation until you cannot do so:

翻译中…
  • Assume the black stone is at $(i, j)$. Perform one of the four operations below:
  • If there is a white stone at $(i, k)$ where $(j < k)$, remove that white stone and move the black stone to $(i, k + 1)$.
    • If there is a white stone at $(i, k)$ where $(j > k)$, remove that white stone and move the black stone to $(i, k - 1)$.
    • If there is a white stone at $(k, j)$ where $(i < k)$, remove that white stone and move the black stone to $(k + 1, j)$.
    • If there is a white stone at $(k, j)$ where $(i > k)$, remove that white stone and move the black stone to $(k - 1, j)$.
    • Here, if the cell to which the black stone is to be moved does not exist, such a move cannot be made.
翻译中…

The following figure illustrates an example. Here, B represents the black stone, W represents a white stone, . represents an empty cell, and O represents a cell to which the black stone can be moved.

翻译中…

..O...
..W...
......
......
..B.WO
......

翻译中…

You win the game if all of the following conditions are satisfied when you finish performing the operation. Otherwise, you lose.

翻译中…
  • All white stones have been removed from the grid.
  • The black stone is placed at $(A, B)$.
翻译中…

In how many initial configurations of the $M$ white stones can you win the game by optimally performing the operation? Find the count modulo $998244353$.

翻译中…

Constraints

翻译中…
  • $2 \leq M \leq N \leq 2 \times 10^5$
  • $1 \leq A \leq N$
  • $1 \leq B \leq N$
  • $N$, $M$, $A$, and $B$ are integers.
翻译中…

Input

翻译中…

The input is given from Standard Input in the following format:

翻译中…

N M A B

翻译中…

Output

翻译中…

Print the number, modulo $998244353$, of possible configurations of the white stones that can lead to your victory.

翻译中…

样例

Input #1
6 4 2 3
Output #1
4
For example, consider the white stones placed as shown in the following figure: Here, you can win the game by moving the black stone in the following steps: - Remove the white stone at $(5, 3)$ and move the black stone to $(6, 3)$. - Remove the white stone at $(6, 5)$ and move the black stone to $(6, 6)$. - Remove the white stone at $(3, 6)$ and move the black stone to $(2, 6)$. - Remove the white stone at $(2, 4)$ and move the black stone to $(2, 3)$. - Since all white stones have been removed from the grid and the black stone is placed at $(A, B) = (2, 3)$, you win the game. There are four configurations of white stones that can lead to your victory.
Input #2
5 3 1 3
Output #2
0
Input #3
200000 47718 21994 98917
Output #3
146958602
题目信息
题号
arc171_e
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。