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$.

  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$.

Input

题意翻译

A 和 B 在网格上游走。 A 要从左上角走到右下角,B 要从左下角走到右下角。 每次指令可以使 A 往右/A 往下/B 往右/B 往上一格。 一格操作序列是好的当且仅当恰有一个时刻 AB 位置相同。 求好的序列个数对 $998244353$ 取模。 translated by cszyf

加入题单

上一题 下一题 算法标签: