atcoder#ARC124F. [ARC124F] Chance Meeting

[ARC124F] Chance Meeting

配点 : 900900

問題文

HHWW 列のマス目が与えられます。 このマス目の上から ii 行目、左から jj 列目のマスを (i,j)(i,j) とします。

はじめ、マス (1,1)(1,1) にラクダが、マス (H,1)(H,1) に猫がいます。

あなたは以下の 44 種類の命令を送ることができます。

  • R: (i,j)(i,j) にいるラクダを (i,j+1)(i,j+1) に移動させる
  • D: (i,j)(i,j) にいるラクダを (i+1,j)(i+1,j) に移動させる
  • r: (i,j)(i,j) にいる猫を (i,j+1)(i,j+1) に移動させる
  • u: (i,j)(i,j) にいる猫を (i1,j)(i-1,j) に移動させる

以下の 44 つの条件全てを満たす命令列を よい命令列 といいます。よい命令列の個数を 998244353998244353 で割ったあまりを求めてください。

  1. ラクダが最終的に (H,W)(H,W) に到達する
  2. 猫が最終的に (1,W)(1,W) に到達する
  3. ラクダと猫が命令による移動後、同じマスにいるということが ちょうど 11 回ある
  4. ラクダや猫がマス目から出ることはない

制約

  • 与えられる入力は全て整数
  • 2H,W2×1052 \leq H,W \leq 2 \times 10^{5}

入力

入力は以下の形式で標準入力から与えられる。

HH WW

出力

よい命令列の個数を 998244353998244353 で割ったあまりを出力せよ。

2 2
16
  • 例えば DRurDurRRruDRDru はよい命令列ですが、DRruRRR などはよい命令列ではありません。
200000 200000
412709667
  • 998244353998244353 で割ったあまりを出力するのを忘れずに。