AtCoder Regular Contest 199 (Div. 1)
D
Limestone
AtCoder
⌀ 3243
原题
← C→
翻译中…

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

翻译中…

样例

Input #1
2 2
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.
Input #2
1 10
Output #2
5120
Input #3
123 456
Output #3
428623282
题目信息
题号
arc199_d
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。