分数: 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