D - Limestone Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1000 点

問題文

正整数 H,W が与えられます．

H 行 W 列の行列 A=(A_{i,j})\ (1\leq i\leq H,1\leq j\leq W) があり，はじめ全ての要素は 0 です．

この行列に対して，以下の 2 種類の操作を好きな順番で何度でも行うことができます．

  • 整数 r,c\ (1\leq r\leq H,1\leq c\leq W) を選ぶ．A_{r,1},A_{r,2},\ldots,A_{r,c} を全て 1 にする．
  • 整数 r,c\ (1\leq r\leq H,1\leq c\leq W) を選ぶ．A_{1,c},A_{2,c},\ldots,A_{r,c} を全て 1 にする．

上記の操作を繰り返して得られる行列全てに対する \displaystyle \sum_{i=1}^H\sum_{j=1}^W A_{i,j} の総和を 998244353 で割った余りを求めてください．

制約

  • 1\leq H,W
  • HW\leq 2\times 10^5
  • 入力は全て整数

入力

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

H W

出力

操作を繰り返して得られる行列全てに対する \displaystyle \sum_{i=1}^H\sum_{j=1}^W A_{i,j} の総和を 998244353 で割った余りを出力せよ．

入力例 1

2 2

出力例 1

29

操作を繰り返して得られる行列は以下の 14 通りあります．

\begin{pmatrix}0&0 \\ 0&0\end{pmatrix} \begin{pmatrix}1&0 \\ 0&0\end{pmatrix} \begin{pmatrix}0&1 \\ 0&0\end{pmatrix} \begin{pmatrix}1&1 \\ 0&0\end{pmatrix} \begin{pmatrix}0&0 \\ 1&0\end{pmatrix} \begin{pmatrix}1&0 \\ 1&0\end{pmatrix} \begin{pmatrix}0&1 \\ 1&0\end{pmatrix} \begin{pmatrix}1&1 \\ 1&0\end{pmatrix} \begin{pmatrix}0&1 \\ 0&1\end{pmatrix} \begin{pmatrix}1&1 \\ 0&1\end{pmatrix} \begin{pmatrix}0&0 \\ 1&1\end{pmatrix} \begin{pmatrix}1&0 \\ 1&1\end{pmatrix} \begin{pmatrix}0&1 \\ 1&1\end{pmatrix} \begin{pmatrix}1&1 \\ 1&1\end{pmatrix}

答えは 0+1+1+2+1+2+2+3+2+3+2+3+3+4=29 です．

\begin{pmatrix}0&0 \\ 0&1\end{pmatrix} や \begin{pmatrix}1&0 \\ 0&1\end{pmatrix} はどのように操作しても得ることができません．

入力例 2

1 10

出力例 2

5120

入力例 3

123 456

出力例 3

428623282

Score : 1000 points

Problem Statement

You are given positive integers H,W.

There is an H \times W matrix A=(A_{i,j})\ (1\leq i\leq H,1\leq j\leq W), where initially all elements are 0.

You can perform the following two types of operations on this matrix in any order and any number of times:

  • Choose integers r,c\ (1\leq r\leq H,1\leq c\leq W). Set all of A_{r,1},A_{r,2},\ldots,A_{r,c} to 1.
  • Choose integers r,c\ (1\leq r\leq H,1\leq c\leq W). Set all of A_{1,c},A_{2,c},\ldots,A_{r,c} to 1.

Find the sum of \displaystyle \sum_{i=1}^H\sum_{j=1}^W A_{i,j} over all matrices that can be obtained by repeating the above operations, modulo 998244353.

Constraints

  • 1\leq H,W
  • HW\leq 2\times 10^5
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

H W

Output

Output the sum of \displaystyle \sum_{i=1}^H\sum_{j=1}^W A_{i,j} over all matrices that can be obtained by repeating the operations, modulo 998244353.

Sample Input 1

2 2

Sample Output 1

29

There are 14 matrices that can be obtained by repeating the operations:

\begin{pmatrix}0&0 \\ 0&0\end{pmatrix} \begin{pmatrix}1&0 \\ 0&0\end{pmatrix} \begin{pmatrix}0&1 \\ 0&0\end{pmatrix} \begin{pmatrix}1&1 \\ 0&0\end{pmatrix} \begin{pmatrix}0&0 \\ 1&0\end{pmatrix} \begin{pmatrix}1&0 \\ 1&0\end{pmatrix} \begin{pmatrix}0&1 \\ 1&0\end{pmatrix} \begin{pmatrix}1&1 \\ 1&0\end{pmatrix} \begin{pmatrix}0&1 \\ 0&1\end{pmatrix} \begin{pmatrix}1&1 \\ 0&1\end{pmatrix} \begin{pmatrix}0&0 \\ 1&1\end{pmatrix} \begin{pmatrix}1&0 \\ 1&1\end{pmatrix} \begin{pmatrix}0&1 \\ 1&1\end{pmatrix} \begin{pmatrix}1&1 \\ 1&1\end{pmatrix}

The answer is 0+1+1+2+1+2+2+3+2+3+2+3+3+4=29.

\begin{pmatrix}0&0 \\ 0&1\end{pmatrix} and \begin{pmatrix}1&0 \\ 0&1\end{pmatrix} cannot be obtained by any sequence of operations.

Sample Input 2

1 10

Sample Output 2

5120

Sample Input 3

123 456

Sample Output 3

428623282