/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
縦 N マス、横 N マスのグリッドがあります。グリッドの上から i 行目、左から j 列目のマスを (i, j) と呼びます。また、 1 個の黒石と M 個の白石があります。
あなたはこれらの道具を使って 1 人でゲームをすることにしました。
ゲームのルールを説明します。はじめに、あなたは黒石を (A, B) に置きます。その後、 M 個の白石をグリッドのいずれかのマスに 1 個ずつ置きます。ただし、
- (A, B) に白石は置けません。
- 白石は 1 つの行に高々 1 個しか置けません。
- 白石は 1 つの列に高々 1 個しか置けません。
その後、あなたは操作を行えなくなるまで以下の操作を行います。
- 黒石が (i, j) にあるとする。次の 4 通りの操作のいずれかを行う。
- (i, k) (j \lt k) に白石が置いてある時、その白石を取り除いて (i, k + 1) に黒石を動かす。
- (i, k) (j \gt k) に白石が置いてある時、その白石を取り除いて (i, k - 1) に黒石を動かす。
- (k, j) (i \lt k) に白石が置いてある時、その白石を取り除いて (k + 1, j) に黒石を動かす。
- (k, j) (i \gt 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) に置かれた状態になったので、あなたはゲームに勝利する。
ゲームに勝利することが可能である白石の配置は全部で 4 通りあります。
入力例 2
5 3 1 3
出力例 2
0
入力例 3
200000 47718 21994 98917
出力例 3
146958602
Score: 800 points
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.
Sample Input 1
6 4 2 3
Sample Output 1
4
For example, consider the white stones placed as shown in the following figure:
...... ..BW.. .....W ...... ..W... ....W.
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.
Sample Input 2
5 3 1 3
Sample Output 2
0
Sample Input 3
200000 47718 21994 98917
Sample Output 3
146958602