201245: [AtCoder]ARC124 F - Chance Meeting
Memory Limit:1024 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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$.