F - Chance Meeting Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 900 点

問題文

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

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

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

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

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

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

制約

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

入力

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

H W

出力

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

入力例 1

2 2

出力例 1

16
  • 例えば DRur、DurR、RruD、RDru はよい命令列ですが、DRru、RRR などはよい命令列ではありません。

入力例 2

200000 200000

出力例 2

412709667
  • 998244353 で割ったあまりを出力するのを忘れずに。

Score : 900 points

Problem Statement

Given is a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

Initially, a camel is on (1, 1), and a cat is on (H, 1).

You can send the following four kinds of orders.

  • R: Move the camel on (i, j) to (i, j+1).
  • D: Move the camel on (i, j) to (i+1, j).
  • r: Move the cat on (i, j) to (i, j+1).
  • u: Move the cat on (i, j) to (i-1, j).

A sequence of orders satisfying all of the four conditions below is said to be good. Find the number of good sequences of orders, modulo 998244353.

  1. The final position of the camel will be (H, W).
  2. The final position of the cat will be (1, W).
  3. The following will happen exactly once: the camel and the cat are on the same square after an order is processed.
  4. Neither the camel nor the cat will leave the grid.

Constraints

  • All values in input are integers.
  • 2 \leq H,W \leq 2 \times 10^{5}

Input

Input is given from Standard Input in the following format:

H W

Output

Print the number of good sequences of orders, modulo 998244353.

Sample Input 1

2 2

Sample Output 1

16
  • The good sequences of orders include DRur, DurR, RruD, RDru, but not DRru, RRR.

Sample Input 2

200000 200000

Sample Output 2

412709667
  • Be sure to print the count modulo 998244353.

OSZAR »