Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 で割ったあまりを求めてください。
- ラクダが最終的に (H,W) に到達する
- 猫が最終的に (1,W) に到達する
- ラクダと猫が命令による移動後、同じマスにいるということが ちょうど 1 回ある
- ラクダや猫がマス目から出ることはない
制約
- 与えられる入力は全て整数
- 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.
- The final position of the camel will be (H, W).
- The final position of the cat will be (1, W).
- The following will happen exactly once: the camel and the cat are on the same square after an order is processed.
- 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 notDRru
,RRR
.
Sample Input 2
200000 200000
Sample Output 2
412709667
- Be sure to print the count modulo 998244353.