AT_arc171_e [ARC171E] Rookhopper's Tour

[problemUrl]: https://atcoder.jp/contests/arc171/tasks/arc171_e 縦 $ 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 $ で割った余りを求めてください。

N/A

N/A

### 制約 - $ 2\ \leq\ M\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ A\ \leq\ N $ - $ 1\ \leq\ B\ \leq\ N $ - $ N,\ M,\ A,\ B $ は整数 ### Sample Explanation 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 $ 通りあります。