← 返回题目列表

AtCoder · arc199_d

D. 石灰石

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

给你正整数 H,W.

有一个 H \times W 矩阵 A=(A_{i,j})\ (1\leq i\leq H,1\leq j\leq W),最初所有元素都是 0.

您可以按任意顺序和任意次数对此矩阵执行以下两种类型的操作:

  • 选择整数 r,c\ (1\leq r\leq H,1\leq c\leq W)。设置全部 A_{r,1},A_{r,2},\ldots,A_{r,c} to 1.
  • 选择整数 r,c\ (1\leq r\leq H,1\leq c\leq W)。设置全部 A_{1,c},A_{2,c},\ldots,A_{r,c} to 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